(Indirect Proof (IP))
Reductio Ad Absurdum (RAA) is a proof technique that takes advantage of our newly found ability to introduce any assumption into a proof at any time (with the proviso that we properly discharge the assumption). You will recall that one way to demonstrate that an argument is valid is to show that the truth of the premises is inconsistent with the falsity of the conclusion. IP exploits this fact by allowing us to demonstrate validity by showing that the premises of an argument together with the negation of the conclusion logically entail contradiction (a statement of the form p ● ~p). In effect, IP simply asks the question "What would happen if the premises of this argument were true while its conclusion was false?" The derived contradiction would have to be true, but that is absurd as the very meaning of a contradiction is that it is always false. Accordingly, the falsity of the conclusion is inconsistent with the truth of the premises, and that is one definition of validity!
Begin an RAA by assuming the negation of the conclusion of the argument. Then, using the standard rules of inference and equivalence, derive a contradiction (a line of the form 'p ● ~p'), then discharge the assumption and derive the conclusion of the argument by a sequence of lines beginning with the assumption of the negation of the conclusion and ending with the derived contradiction. As with CP, a vertical line beginning with the assumption and ending with the contradiction marks the scope of the assumption.
RAA works because the derived contradiction is obviously false. Since it is impossible to derive falsity from truth ( and the premises are assumed to be true), the source of the falsity obvious in the contradiction must be the assumption of the negation of the conclusion. But if that assumption is false, then the conclusion is true if the premises are, but that is just the definition of a valid argument.
RAA, reductio ad absurdum, is Latin for "reduction to absurdity." One of the fundamental rules of logic is that one can NEVER derive falsity from truth. True premises together with proper reasoning guarantees a true conclusion. As a historical matter, indirect proof has played a major role in the development of Western thinking and mathematics. Attempts by Reimann and Lobaschevsky to prove Euclid's parallel postulate through IP lead to the development of non-Euclidian geometry. Schematically, this is the form of an IP:
To prove ~Φ To prove Φ 1. Premises 1. Premises 2. Φ Assumption 2. ~Φ Assumption 3 ... Derived line 3 ... Derived line 4 ... Derived line 4 ... Derived line n Ψ ● ~Ψ Derived line n Ψ ● ~Ψ Derived line q. ~Φ 2-n IP q. Φ 2-n RAA
To see how IP works, let's use it to prove that Modus Ponens is a valid argument form. NOTE, for this example I cannot use MP as a justification for a line--the legitimacy of the inference is what is at issue
1. p → q premise 2. p premise 3. ~q AP 4. ~p ▼ q 1 MI 5. ~p 3,4 DS 6. p ● ~p 2,5 Conj 7. q 3-6 RAA
Since this argument with the extra assumed premise logically implies a contradiction, it has inconsistent premises and so at least one of its premises must be false. Suppose the premises of the original argument are true. Then it is must be the assumed premise false. But if the assumed premise, ~q, is false, then the original conclusion, q, must be true. Hence, if the original argument has true premises, then its conclusion must be true, too (i.e., it is valid).
IP often provides a clearer and more obvious proof that a direct proof. Consider the following argument:
Direct Proof Indirect Proof A → B, A ▼ B ∴B A → B, A ▼ B ∴B 1. A → B premise 1. A → B premise 2. A ▼ B premise 2. A ▼ B premise 3 B ▼ A 2 comm 3. ~B AP 4. ~ ~ B ▼ A 3 DN 4. A 2,3 DS 5. ~ B → A 4 MI 6. B 1,4 MP 6. ~ B → B 1,5 HS 7. B ● ~B 3,6 Conj 7. ~ ~ B ▼ B 6 MI 8. B 3-7 IRAA 8. B ▼ B 7 DN 9. B 8 Taut
The IP not only takes fewer steps, but it uses rules with which many of you will feel more comfortable. Just to drive home how valuable IP can be, here is one more IP derivation. Try to construct on your own a direct proof for this argument.
(A → B) → C, (A ● ~B) → C ∴ C
1. (A → B) → C ∴ C
2. (A ● ~B) → C
→3. ~C AP
| 4. ~(A → B) 1,3 MT
| 5. ~(A ● ~B) 2,3 MT
| 6. ~A ▼ ~~B 5 DeM
| 7. ~A ▼ B 6 DN
| 8. A → B 7 Cond
| 9. (A → B) ● ~(A→ B) 8,4 Conj
10. C 3-9 IP
Here is the direct proof.
Return to Tutorials Index