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

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?

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.

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.