We have a calculus $\vdash$ in the set $\mathcal{F}\{\vee\}$ of propositional formulas with the signature $\{\vee\}$. It has the following four unary Hilbert-style rules:

$$ \begin{align} (1)\ \alpha/\alpha\vee\beta,\quad (2)\ \alpha\vee\alpha/\alpha,\quad (3)\ \alpha\vee\beta/\beta\vee\alpha,\quad (4)\ \alpha\vee(\beta\vee\gamma)/(\alpha\vee\beta)\vee\gamma \end{align} $$

I am supposed to prove the following:

$$ \alpha\vdash\beta \Rightarrow \alpha\vee\gamma\vdash\beta\vee\gamma $$

I don't know how to do this at all. I don't know how to even start to make statements about $\alpha\vee\gamma$, as I haven't been given any tautologies acting as a logical axiom scheme, and applying the four rules of inference to $\alpha\vdash\beta$ only lets me make further conclusions as to what we can derive from $\alpha$, but not from $\alpha\vee\gamma$.

This is a part of exercise 4 in chapter 1.6 of A Concise Introduction to Mathematical Logic by Wolfgang Rautenberg. The whole exercise is to prove completeness of the calculus $\vdash$, and the solutions manual states that the first step is to prove the property above.

Edit: Can I do the following?

$$ \begin{align} \alpha\vee\gamma&\vdash(\alpha\vee\gamma)\vee\beta&(1)\\ &\vdash\alpha\vee(\gamma\vee\beta)&(4)\\ \end{align} $$

And if yes, how do I get rid of the $\alpha$? Can I use that $\alpha\vdash\beta\vee\gamma$? How and why?


1 Answer 1


Hint: I don't know about Hilbert-style, but in ordinary propositional logic, you could start with the assumption that $A\implies B$, then a 2nd assumption $B \lor C$ which will give you two cases to consider.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.