[Math] Prove a Contraposition with natural deduction

discrete mathematicselementary-set-theorylogicnatural-deductionproof-explanation

I'm studying for a test and I wanted to double check some work I've done on one of the harder review questions. The question is asking me to prove the following the following contraposition:

$\lnot P \to \lnot Q \Rightarrow Q \to P$

using natural deduction system N. The rules given by the instructor include the elimination rules, the introduction rules, the contradiction rule, and the weakening rule. Here's my work, with the rules noted in parenthesis along with the line numbers used:

  1. Axiom: $\lnot P \to \lnot Q \Rightarrow \lnot P \to \lnot Q$
  2. Axiom: $\lnot P \Rightarrow \lnot P$
  3. ($\to E$ 1,2): $\lnot P, \lnot P \to \lnot Q \Rightarrow \lnot Q$
  4. Axiom: $Q \Rightarrow Q$
  5. ($\lnot E$ 3,4) $Q, \lnot P, \lnot P \to \lnot Q \Rightarrow$
  6. ($\lnot I$ 5) $Q, \lnot P \to \lnot Q \Rightarrow \lnot\lnot P$
  7. Axiom: $\lnot\lnot P \Rightarrow \lnot\lnot P$
  8. Axiom: $\Rightarrow P \lor\lnot P$
  9. Axiom: $P \Rightarrow P$
  10. Axiom: $\lnot P \Rightarrow \lnot P$
  11. ($\lnot E$ 7, 10) $\lnot\lnot P, P \Rightarrow$
  12. (C 11) $\lnot\lnot P, \lnot P \Rightarrow P$
  13. ($\lor E$ 8, 9, 12) $\lnot\lnot P \Rightarrow P$
  14. ( $\to I$, 13) $\lnot\lnot P \to P$
  15. ($\to E$ 6, 14) $Q, \lnot P \to \lnot Q \Rightarrow P$
  16. ($\to I$ 15) $\lnot P \to \lnot Q \Rightarrow Q \to P$

I'm pretty sure this is accurate, but with so many steps I'd appreciate it if there's something I missed.

Best Answer

You have a typo on line 11, which should be:

$\neg \neg P, \neg P \Rightarrow$

But other than that everything looks fine!! I don't know system N, so I can't attest to whether or not you applied the rules defined for it correctly, but at least logically everything checks out!

Related Question