2
$\begingroup$

I'm going through the exercises in the book "A problem course in mathematical logic", chp 3, ex 3.9. and I'm struggling to understand how to solve the following task:

Based on the deduction theorem and the axioms:

  • $(\alpha \rightarrow (\beta \rightarrow \alpha))$
  • $((\alpha \rightarrow (\beta \rightarrow \gamma)) \rightarrow ((\alpha \rightarrow \beta) \rightarrow (\alpha \rightarrow \gamma)))$
  • $(((\lnot\beta) \rightarrow (\lnot\alpha)) \rightarrow (((\lnot \beta) \rightarrow \alpha) \rightarrow \beta))$

show that:

$\{\delta,\lnot\delta\}\vdash\gamma$

The hint, that is given in the book, is to use the last axiom, but I don't really get it, how can we prove $\gamma$ if it's not even in the set to the left?

$\endgroup$
5
  • $\begingroup$ It's easier for you to find a formal proof if you recognize this is the famous Principle of explosion in classic logic... $\endgroup$
    – mohottnad
    Sep 28, 2021 at 22:33
  • $\begingroup$ I see, that comes from the assumption that all formulas in the set to the left should be true, which is false -> we can prove anything from false. $\endgroup$
    – Def_NulL
    Sep 28, 2021 at 22:41
  • $\begingroup$ U got it... Can you spot what is the famous philosophical principle of your first theorem in your book? $\endgroup$
    – mohottnad
    Sep 28, 2021 at 22:44
  • $\begingroup$ It's probably not the "Unique Readability Theorem", that you meant, which appears to be the first theorem in that book. $\endgroup$
    – Def_NulL
    Sep 28, 2021 at 22:50
  • $\begingroup$ Nope, it's not Enderton's unique readability theorem since β is clearly not uniquely determined by α, but good try and on track... (hint, you may read Leibniz). I mean the first theorem of your above question, I don't really mean your book. $\endgroup$
    – mohottnad
    Sep 28, 2021 at 22:59

1 Answer 1

2
$\begingroup$

First, prove that $\{\delta, \neg \delta\} \vdash \neg \gamma \to \delta$.

Then, prove that $\{\delta, \neg \delta\} \vdash \neg \gamma \to \neg \delta$.

Both of these are done using rule 1 and modus ponens.

Then, conclude that $\{\delta, \neg \delta\} \vdash (\neg \gamma \to \neg \delta) \to ((\neg \gamma \to \delta) \to \gamma)$ using rule 3.

Finally, apply modus ponens twice more to conclude $\{\delta, \neg \delta\} \vdash \gamma$.

$\endgroup$
3
  • $\begingroup$ It seems I miss something fundamental. We could have proved {𝛿,¬𝛿}⊢¬𝛾 in the same way, right? And another question, how would we prove the first step that you suggested? $\endgroup$
    – Def_NulL
    Sep 28, 2021 at 22:28
  • $\begingroup$ @Def_NulL The point is that we can prove $\{\delta, \neg \delta\} \vdash \gamma$ no matter what $\delta, \gamma$ are. So yes, we could prove $\{\delta, \neg \delta\} \vdash \neg \gamma$. For the first step, use rule 1 to conclude $\{\delta, \neg \delta\} \vdash \delta \to (\neg \gamma \to \delta)$. Then apply modus ponens. $\endgroup$ Sep 28, 2021 at 22:30
  • $\begingroup$ Thanks Mark, I guess I need to reread Deduction part of the book once again, or look for more verbose explanation to understand how we are allowed to manipulate formulas in order to prove with the deduction theorem. $\endgroup$
    – Def_NulL
    Sep 28, 2021 at 22:43

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.