A proof in the Hilbert-style axiom system

1. Oct 25, 2016

PWiz

1. The problem statement, all variables and given/known data
Provide a complete formal proof that $\vdash ((A \rightarrow B) \rightarrow C) \rightarrow (B \rightarrow C)$.
2. Relevant equations
I am only allowed to use modus ponens and these four 'sentential logic' axioms:
A1 $\neg \alpha \rightarrow (\alpha \rightarrow \beta)$
A2 $\beta \rightarrow (\alpha \rightarrow \beta)$
A3 $(\alpha \rightarrow \beta) \rightarrow ((\neg \alpha \rightarrow \beta) \rightarrow \beta)$
A4 $(\alpha \rightarrow (\beta \rightarrow \gamma )) \rightarrow ((\alpha \rightarrow \beta) \rightarrow (\alpha \rightarrow \gamma ))$

3. The attempt at a solution
I have no idea where to begin. I'm thinking about using axiom 2, but I don't know how I would proceed from there. The problem would become easy if I was allowed to 'add an antecedent', but I am not allowed to directly do that. Any help is appreciated. Please note that I am a new student to logic, and I have only studied zero-order logic until now, so kindly provide hints that I will be able to understand. (The homework is due tomorrow!)

2. Oct 25, 2016

stevendaryl

Staff Emeritus
These kind of proofs are much easier if you have the deduction theorem. What the deduction theorem says is that:

If you can prove $Y$ using $X$ as an axiom, then you can prove $X \rightarrow Y$​

You don't have the deduction theorem, but you can use it as a strategy for finding the proof, as follows:

A proof of $S$ is a sequence of statements $S_1, S_2, ..., S_n$ such that each statement is either an axiom, or follows from two previous statements by modus ponens, and such that the last statement is $S$. So:
1. See if you can construct a proof of $C$ where the first statement is $(A \rightarrow B) \rightarrow C$ and the second statement is $B$. So this original proof will have $C$ as its last sentence.
2. Now, modify your proof as follows: Starting with the third statement, replace each statement $S$ by the modified statement $B \rightarrow S$. Now, see if you can add additional steps so that you prove each modified statement without using $B$ as an axiom. After these modifications, you will have a proof where $B \rightarrow C$ is the last statement.
3. Now, modify your proof again: Starting with the new third statement, replace each statement $S$ by the modified statement $((A \rightarrow B) \rightarrow C) \rightarrow S$. Now, see if you can add additional steps so that you can prove each modified statement without using $(A \rightarrow B) \rightarrow C$ as an axiom. After these modifications, you will have a proof where $((A \rightarrow B) \rightarrow C) \rightarrow (B \rightarrow C)$ is the last statement.
4. Now, get rid of the first two statements, since you are no longer using them. Now you have a proof of $((A \rightarrow B) \rightarrow C) \rightarrow (B \rightarrow C)$

3. Oct 30, 2016

PWiz

Thanks, I got it!