[Math] Proof using Reductio ad absurdum (RAA)

logic

Note: $\neg$ means 'not', $\rightarrow$ is 'conditional', $\land$ is 'and', $\lor$ means '(inclusive) or'.

Prove: $[\neg D \lor (A \land B)] \rightarrow[(J \rightarrow \neg A) \rightarrow (D \rightarrow \neg J)]$ using Reductio ad absurdum (RAA) or conditional proof (CP).

  1. $\neg[(J \rightarrow \neg A) \rightarrow (D \rightarrow \neg J)]$ (Assume for RAA)
  2. $(J \rightarrow \neg A) \land \neg(D \rightarrow \neg J)$ (Equation 1 is only false if the the left is true and the right is false)
  3. $\neg(D \rightarrow \neg J)$ (simplification of equation 2, I think)
  4. $D \land \neg\neg J$ (the only way for eq 3 to be true is if $D$ is true and $\neg J$ is false ).
  5. $D$ (simplification of 4)
  6. $\neg\neg J$ (simplification of 4)
  7. $J$ (double negative of 6).
  8. $J \rightarrow \neg A$ (simplification of left term equation 2
  9. $\neg A$ (eq 7, 8, $J$ is true, so $\neg A$ is true).
  10. $\neg(A \land B)$ (if $A$ is false, $A$ and anything is false, negate that to get a true)
  11. $\neg[\neg D \vee (A \land B)]$ ($A\land B$ is false, from eq 10, and $D$ is true from eq 5, $\neg D$ is false, false and false is false)

12 $\neg [(J \rightarrow \neg A) \rightarrow (D \rightarrow \neg J)] \rightarrow \neg[\neg D \lor (A \land B)]$ (1-11, RAA)

13 $[\neg D \lor (A \land B)] \rightarrow [(J \rightarrow \neg A) \rightarrow (D \rightarrow \neg J)]$ (contrapositive of eq 12)

What's wrong with the above proof? The teacher said it did not use RAA or CP and gave 0 points. Why not?

Best Answer

In a proof by reductio ad absurdum, you begin by assuming the negation of the proposition to be proven; in this case, you would begin by assuming $$\neg\Bigl([\neg D \lor (A \land B)] \longrightarrow[(J \rightarrow \neg A) \rightarrow (D \rightarrow \neg J)]\Bigr).$$ The objective is to deduce an absurdity (something of the form $P\land \neg P$). As you can see, you don't do either of those (you neither start with the negation of the proposition to be proven, nor do you deduce an absurdity), so you did not give a proof by reductio ad absurdum.

In a "conditional proof" of $P\to Q$, you assume $P$, and then you proceed to deduce $Q$. From this proof, thanks to the Deduction Metatheorem, you can conclude that there is a proof of $P\to Q$. In the case at hand, your proof would have to begin by assuming $$\neg D\lor (A\land B)$$ and finish by deducing $$(J\to \neg A)\to(D\to\neg J).$$ Again, as you can see, you did not do this.

So I think that "what is wrong" with your proof is that it did not follow the instructions given; you were asked to produce a proof by one of two methods, and you did not. That is not to say your proof is invalid: from what I can tell, it is a valid proof. You provided a conditional proof of the contrapositive of the proposition you want to establish. Unfortunately, a conditional proof of the contrapositive is neither a conditional proof, nor a reductio ad absurdum proof. As to partial marks, that's up to your instructor.

Now, don't despair: it is fairly easy to turn your proof into a proof by reductio ad absurdum. Start with the negation of the proposition you have; you will be able to deduce from this assumption your line 1. Having deduced your line 1, you will end up, with your development, deducing $\neg(\neg D\lor (A\land B))$. Now, form the original assumption you should also be able to deduce $(\neg D\lor (A\land B))$, and now you are in the situation you wish: you will have $P\land \neg P$, with $P\equiv (\neg D\lor (A\land B))$.

Related Question