# 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!