Prove $\emptyset \vdash(\alpha\rightarrow (\neg\alpha\rightarrow \neg \beta))$.

Question

Prove $\emptyset \vdash(\alpha\rightarrow (\neg\alpha\rightarrow \neg \beta))$.

Using the axioms:

1. $(\phi \rightarrow(\psi \rightarrow \phi))$
2. $((\phi\rightarrow(\psi\rightarrow\gamma))\rightarrow((\phi\rightarrow\psi)\rightarrow(\phi\rightarrow\gamma)))$
3. $ ((\neg \phi \rightarrow\neg \psi)\rightarrow((\neg \phi \rightarrow\psi)\rightarrow\phi)))$

And the inference rule modus ponens.

A proof in this manner means a sequence of lines where each line is an axiom, or a formula from your "base" set ($\{\alpha,\neg\alpha\}$ below), or an inference (using modus ponens), with the last line being the formula being proved.

I used the deduction theorem to say that a finding a proof from the empty set of that formula is equivalent to finding a proof:

$$\{\alpha,\neg\alpha\}\vdash\neg\beta$$

And I tried at least 15 times but I couldn't arrive at one.

Also, could you guys give me some general tips on how to construct these proofs? By this I mean, is there any systematic approach to these problems?

Answer 1

Using base set $\{\alpha,\lnot\alpha\}$, from 1. deduce $\beta\to\alpha$ and $\beta\to\lnot\alpha$, then apply 3. with $\phi=\lnot\beta$.

Answer 2

If you by "base" set means the left side of the $\vdash$ and you get to use the deduction theorem you can simply use the fact that with contradictions in the premise anything can be proved via reductio ad absurdum (ie axiom 3):

$\alpha, \neg\alpha, \neg\neg\beta \vdash \alpha$

$\alpha, \neg\alpha \vdash \neg\neg\beta \rightarrow \alpha $

and similarily

$\alpha, \neg\alpha \vdash \neg\neg\beta \rightarrow \neg\alpha $

Therby via modens ponens

$\alpha, \neg\alpha \vdash (\neg\neg\beta \rightarrow \neg\alpha) \rightarrow ((\neg\neg\beta \rightarrow \alpha) \rightarrow \neg\beta $

$\alpha, \neg\alpha \vdash (\neg\neg\beta \rightarrow \alpha) \rightarrow \neg\beta$

And modus ponens again:

$\alpha, \neg\alpha \vdash \neg\beta$

But did you really get to use the deduction theorem?

If you didn't get to use the deduction theorem you would basically have to rewrite the $\vdash$ notation to implication notation, but you have to take care here since implication notation doesn't allow us to reorder the prerequisites yet. We have to prove that, at least in a weaker sense since we only use one prerequisite at a time. We need that $(\phi\rightarrow \psi)\rightarrow(\phi\rightarrow (\gamma\rightarrow \psi))$, especially for the first step:

1. $\psi\rightarrow(\gamma\rightarrow\psi)$
2. $\phi\rightarrow(\psi\rightarrow(\gamma\rightarrow\psi))$
3. $\phi\rightarrow(\psi\rightarrow(\gamma\rightarrow\psi)) \rightarrow ((\phi\rightarrow\psi)\rightarrow(\phi\rightarrow(\gamma\rightarrow\psi)))$
4. $(\phi\rightarrow\psi)\rightarrow(\phi\rightarrow(\gamma\rightarrow\psi))$

Now it's clear that since $\alpha\rightarrow(\neg\neg\beta\rightarrow\alpha)$ it follows that $\alpha\rightarrow(\neg\alpha\rightarrow(\neg\neg\beta\rightarrow\alpha))$