$\Sigma$ is a set of sentences, the set $\mathcal{L}$ consists of all axioms of the forms:

A1) $\phi \rightarrow (\psi \rightarrow \phi)$

A2) $(\phi \rightarrow (\psi \rightarrow \theta)) \rightarrow ((\phi \rightarrow \psi) \rightarrow (\phi \rightarrow \theta))$

A3) $((\lnot \phi \rightarrow \psi) \rightarrow (( \lnot \phi \rightarrow \lnot \psi) \rightarrow \phi))$

*I can only use $\rightarrow$ with modus ponens.

I need to prove this and I would like some hints. I can get by Deduction theorem, $\Sigma \vdash \phi \rightarrow \theta$ and $\Sigma \vdash \lnot\phi \rightarrow \theta$. I think you need to use A3 with $\phi$ as $\theta$, but I'm not quite sure what else.

  • $\begingroup$ What's the question? $\endgroup$ – Angina Seng Sep 21 '18 at 3:52
  • 1
    $\begingroup$ See your post : you need the same preliminary work, and also contraposition : B6) $\vdash (\phi \to \psi) \to (\lnot \psi \to \lnot \phi)$. $\endgroup$ – Mauro ALLEGRANZA Sep 21 '18 at 8:29
  • 1
    $\begingroup$ Thus, byDT we have $\Sigma \vdash (\phi \to \theta)$ and $\Sigma \vdash (\lnot \phi \to \theta)$. $\endgroup$ – Mauro ALLEGRANZA Sep 21 '18 at 8:30
  • 1
    $\begingroup$ By contraposition : $\Sigma \vdash (\lnot \theta \to \lnot \phi)$ and $\Sigma \vdash (\lnot \theta \to \lnot \lnot \phi)$. $\endgroup$ – Mauro ALLEGRANZA Sep 21 '18 at 8:31
  • 1
    $\begingroup$ Finally, use a suitable instance of A3). $\endgroup$ – Mauro ALLEGRANZA Sep 21 '18 at 8:32

For deduction theorem $\Sigma \vdash \phi \rightarrow \theta$ and $\Sigma \vdash \neg \phi \rightarrow \theta$, then $\Sigma \vdash \phi \wedge \neg \phi \rightarrow \theta$, but $\Sigma \not\vdash \phi \wedge \neg \phi$.

  • $\begingroup$ Oh shoot. I forgot to add I can only use $\rightarrow$ and modus ponens. $\endgroup$ – Timelined Sep 21 '18 at 4:03
  • $\begingroup$ Don't forget that $\phi \rightarrow \theta$ is equivalent to $\neg \phi \vee \theta$. $\endgroup$ – Tom Ryddle Sep 21 '18 at 4:09
  • 1
    $\begingroup$ Does $\Sigma \vdash \phi \wedge \neg \phi \rightarrow \theta$ mean $\Sigma \vdash$ both $\phi$ and $\neg \phi \rightarrow \theta$. If so how did you get $\Sigma \vdash \phi$ $\endgroup$ – Timelined Sep 21 '18 at 4:22

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.