2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What do you mean with "base" set? $\endgroup$ – skyking Sep 25 '15 at 7:44
3
$\begingroup$

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

$\endgroup$
  • $\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$ – YoTengoUnLCD Sep 23 '15 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$ – YoTengoUnLCD Sep 23 '15 at 22:56
  • 1
    $\begingroup$ Yes, you're right $\endgroup$ – Berci Sep 23 '15 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$ – YoTengoUnLCD Sep 23 '15 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 Sep 27 '15 at 12:08
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.