Proof by Contradiction

    A contradiction is a statement which is false no matter what the truth value of its constituent parts. It can usually be expressed symbolically in the form . A proof by contradiction of a statement P is a proof that assumes and yields a sentence of the type , where R is any sentence including P, an axiom, or any previously proved theorem. This is justified by the tautology

Intuitively, P can only be true or false (since we are assuming only a two-valued logic). If we assume its negation true and this yields another sentence both true and false, then cannot be true, so P must be true.

The phrases reductio ad absurdum  and indirect proof  both refer to proof by contradiction. The importance of being able to form sentence negations is realized when doing proofs by contradiction. To begin such proofs you must know how to form negations.

Comparing proof techniques we see that with the Rule of Conditional Proof we assume P with the explicit intention of deducing Q. With the contrapositive we assume with the explicit intention of deducing . But in using Proof by Contradiction we assume both P and and try to deduce any sentence R and its negation .