Prove that $\alpha\vdash\beta$ implies $\alpha\vee\gamma\vdash\beta\vee\gamma$ using four unary Hilbert-style rules of inference.

Question

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?

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.

Answer 2

Hint:

$\alpha \vdash \beta$ can be obtained by any of the four rules, a sketch of the induction:

$$\alpha\gamma \vdash \gamma \alpha\vdash (\gamma\alpha)\beta \vdash \gamma(\alpha\beta)\vdash (\alpha \beta)\gamma$$

put $\alpha_0=\alpha,\; \beta_0 = \alpha\beta$, we have $\alpha_0 \vdash \beta_0 \implies \alpha_0\gamma \vdash \beta_0 \gamma$ under rule (1).

(This has actually been given by the original hints.)

$$(\alpha\alpha)\gamma \vdash \alpha(\alpha\gamma)\vdash (\alpha\gamma)\alpha\vdash((\alpha\gamma)\alpha)\gamma\vdash (\alpha\gamma)(\alpha\gamma)\vdash\alpha\gamma $$

put $\alpha_0=\alpha\alpha,\; \beta_0 = \alpha$, we have $\alpha_0 \vdash \beta_0 \implies \alpha_0\gamma \vdash \beta_0 \gamma$ under rule (2).

Do the same for (3) and (4), note that for the above proof, $ (\gamma\alpha)\beta \vdash \gamma(\alpha\beta)$ needs to be shown first.