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:


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?

  • $\begingroup$ What do you mean with "base" set? $\endgroup$
    – skyking
    Commented Sep 25, 2015 at 7:44

2 Answers 2


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

  • $\begingroup$ Hi, thanks a lot, but to do that I'd need to use $\beta \equiv \neg \neg \beta$, right? I'm not allowed to use that, unfortunately. $\endgroup$ Commented Sep 23, 2015 at 22:53
  • 1
    $\begingroup$ Oh I just realized, I can deduce $\neg \neg \beta \implies \alpha$ and $\neg \neg \beta \implies \neg \alpha$ and arrive at the result without using that equivalence, right? $\endgroup$ Commented Sep 23, 2015 at 22:56
  • 1
    $\begingroup$ Yes, you're right $\endgroup$
    – Berci
    Commented Sep 23, 2015 at 22:58
  • $\begingroup$ May I ask how you thought of it? I've had lots of troubles being able to complete these proofs. $\endgroup$ Commented Sep 23, 2015 at 22:59
  • $\begingroup$ I was looking at where could we ever obtain the formula $\lnot\beta$. And I saw the only chance is from axiom 3. with $\phi=\lnot\beta$, as 1. and 2. produce formulas of the form $\phi\to\psi$ even after modus ponens applied. Now, to use 3. we just need the two premises $\lnot\lnot\beta\to\alpha$ and $\lnot\lnot\beta\to\lnot\alpha$ which can come from 1. $\endgroup$
    – Berci
    Commented Sep 27, 2015 at 12:08

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))$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .