# Proof using Reductio ad absurdum (RAA)

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?

-
Instead of using less-standard notation and explaining it at the end, how about using the standard symbols from the start? – Asaf Karagila Jul 22 '12 at 20:17
\neg produces $\neg$; \land produces $\land$; \lor produces $\lor$ (better than \vee and \wedge, because of spacing issues). – Arturo Magidin Jul 22 '12 at 20:19
The instructions explicitly say you should be doing the proof either by contradiction, or as conditional proof; you instead did the proof by using conditional proof on the contrapositive. To get a proof by contradiction, you must assume the negation of what you want to show, and not just of the consequent, and you must obtain an absurdity at some point (you didn't, but it would be easy to do with what you have). To get a conditional proof, you would have to start with the premise, not the negation of the conclusion. So what is wrong is that it didn't follow the instructions given. – Arturo Magidin Jul 22 '12 at 20:22
@Jeff: Yes; so then the problem is that you are not doing a proof by reductio ad absurdum, even though you claim you are. Since what you are trying to do is prove the implication, an RAA proof would start by assuming the negation of the whole implication, not just the consequent. Alternatively, you can start by applying CP (the Deduction Theorem) and assume the antecedent; then in order to prove the consequent is true, you can use RAA by assuming the consequent is false. But this is "really" the same as assuming the negation of the implication, and then deducing premise and not(consequent). – Arturo Magidin Jul 22 '12 at 20:47
Note also that, depending on your instructor, some of the justifications might be lacking; e.g., a better way to justify 10 is to go from $\neg A$ to $\neg A\lor \neg B$ (by $\lor$-introduction), and then to $\neg(A\land B)$ by De Morgan's law. – Arturo Magidin Jul 22 '12 at 21:03

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

-
Good answer. Q: Isn't your last paragraph using both RAA and CP? You negated the proposition to get to my line 1 (RAA), and argued to a statement which contradicted the proposition's antecedent. That means you must have assumed the proposition's antecedent, which sounds like CP. – Jeff Jul 22 '12 at 21:02
@Jeff: No, I didn't say you negate the proposition to get your line 1. I said, negate the proposition. From that negation, one can deduce your line 1 (because the negation of the proposition will be of the form $A\land \neg B$, and your line 1 is precisely $\neg B$). You can also deduce $A$ from $A\land\neg B$. Your development allows you to also deduce $\neg A$ from $A\land\neg B$ (or more precisely, from just $\neg B$); so then from $A\land\neg B$ we get $A$ and we also get $\neg A$, which gives $A\land\neg A$, and that's the contradiction. – Arturo Magidin Jul 22 '12 at 21:05
Thanks (I'm just getting back to this now). OK, so the negation of a conditional, $A \rightarrow B$ is $\neg(A \rightarrow B) \equiv A \land \neg B$? I think my proof was correct. I just mislabeled CP as RAA. If I had called it CP, then I could say I've proven line 12 using CP and then line 13 by contrapostive of 12. So this proof even followed my (incorrect, but more restrictive) instructions. Either way, we're going back to get partial credit! – Jeff Jul 25 '12 at 2:04
@Jeff: Yes, the negation of $A\to B$ is $A\land \neg B$. No, you did not do a proof by CP, because along the way you are assuming $\neg B$; that is not a proof by CP, because in a proof by CP you are not allowed to assume $\neg B$. You would only be able to assume $A$. So I disagree with your claim that you "just mislabeled". As for partial credit, that's between you and your instructor, so I hope you will not cite this thread as an argument in your favor. – Arturo Magidin Jul 25 '12 at 2:51
Well, I proved the contrapositive by CP. And no, I wouldn't cite this thread. – Jeff Jul 25 '12 at 15:15

A conditional proof is more straightforward. Following up on Arturo's suggestion for a conditional proof, begin as follows:

1. $\neg D \lor (A \land B)$ (Assume)

2. $J \rightarrow \neg A$ (Assume)

3. $D$ (Assume)

It is then quite easy to obtain the required result by direct proof.

See my proof at: http://www.dcproof.com/Jeff.htm

-
So what is the order of assumptions for $[\neg D \lor (A \land B)] \rightarrow [(J \rightarrow \neg A) \rightarrow (D \rightarrow \neg J)]$? – Jeff Jul 27 '12 at 5:46
In the order indicated above. – Dan Christensen Jul 30 '12 at 4:44
Oops! I put the wrong problem in the comment. No matter, I got it all done now. Thx for helpin'. – Jeff Jul 30 '12 at 21:16