# How to prove $((A \to B) \to A) \to A$ using Lukasiewicz's axioms, MP and deduction theorem?

This is an exercise from A.G. Hamilton's Logic for Mathematicians, section 2.1, p. 36. I have tried to do this for 10 long years, since 2010. Unsuccessful.

Exercise 3: Using the deduction theorem for $$L$$, show that the following wfs. are theorems of $$L$$, where $$\mathcal{A}$$ and $$\mathcal{B}$$ are any wfs of $$L$$.

(c) $$((\mathcal{A} \to \mathcal{B}) \to \mathcal{A}) \to \mathcal{A}$$

The axiom schemes of $$L$$ are:

1. $$\mathcal{A} \to (\mathcal{B} \to \mathcal{A})$$.
2. $$\mathcal{A} \to (\mathcal{B} \to \mathcal{C}) \to ((\mathcal{A} \to \mathcal{B}) \to (\mathcal{A} \to \mathcal{C}))$$.
3. $$((\sim \mathcal{A}) \to (\sim \mathcal{B})) \to (\mathcal{B} \to \mathcal{A})$$.

The only rule of inference of $$L$$ is modus ponens (MP): from $$\mathcal{A}$$ and $$\mathcal{A} \to \mathcal{B}$$, deduce $$\mathcal{B}$$.

The deduction theorem for $$L$$ says: if $$\Gamma \cup \{\mathcal{A}\} \vdash \mathcal{B}$$, then $$\Gamma \vdash (\mathcal{A} \to \mathcal{B})$$.

Thanks for helping me.

The statement is known as Peirce's Law, and the proof is pretty nasty. I can believe someone can spend $$10$$ years on it without cracking it!

The proof uses some helpful Lemma's.

First, let's prove: $$\phi \to \psi, \psi \to \chi, \phi \vdash \chi$$:

1. $$\phi \to \psi$$ Premise

2. $$\psi \to \chi$$ Premise

3. $$\phi$$ Premise

4. $$\psi$$ MP 1,3

5. $$\chi$$ MP 2,4

By the Deduction Theorem, this gives us Hypothetical Syllogism (HS): $$\phi \to \psi, \psi \to \chi \vdash \phi \to \chi$$

Now let's prove the general principle that $$\neg \phi \vdash (\phi \to \psi)$$:

1. $$\neg \phi$$ Premise

2. $$\neg \phi \to (\neg \psi \to \neg \phi)$$ Axiom1

3. $$\neg \psi \to \neg \phi$$ MP 1,2

4. $$(\neg \psi \to \neg \phi) \to (\phi \to \psi)$$ Axiom2

5. $$\phi \to \psi$$ MP 3,4

With the Deduction Theorem, this means $$\vdash \neg \phi \to (\phi \to \psi)$$ (Duns Scotus Law)

Let's use Duns Scotus to show that $$\neg \phi \to \phi \vdash \phi$$ (Law of Clavius):

1. $$\neg \phi \to \phi$$ Premise

2. $$\neg \phi \to (\phi \to \neg (\neg \phi \to \phi))$$ (Duns Scotus Law)

3. $$(\neg \phi \to (\phi \to \neg (\neg \phi \to \phi))) \to ((\neg \phi \to \phi) \to (\neg \phi \to \neg (\neg \phi \to \phi)))$$ Axiom3

4. $$(\neg \phi \to \phi) \to (\neg \phi \to \neg (\neg \phi \to \phi))$$ MP 2,3

5. $$\neg \phi \to \neg (\neg \phi \to \phi)$$ MP 1,4

6. $$(\neg \phi \to \neg (\neg \phi \to \phi)) \to ((\neg \phi \to \phi) \to \phi)$$ Axiom2

7. $$(\neg \phi \to \phi) \to \phi$$ MP 5,6

8. $$\phi$$ MP 1,7

Using Duns Scotus and the Law of Clavius, we can now show that $$(\phi \to \psi) \to \phi \vdash \phi$$:

1. $$(\phi \to \psi) \to \phi$$ Premise

2. $$\neg \phi \to (\phi \to \psi)$$ Duns Scotus

3. $$\neg \phi \to \phi$$ HS 1,2

4. $$\phi$$ Law of Clavius 3

And so finally, by the Deduction Theorem, we have: $$\vdash ((\phi \to \psi) \to \phi) \to \phi$$