Proof by Reductio Ad Absurdum
Proof by reductio ad absurdum is also known as proof by contradiction. It is one of the most powerful tools of reasoning at the disposal of logicians and mathematicians. Reductio proofs are used for conditionals, propositions of the form "if p then q." Most mathematical theorems take this form, for instance the Pythagorean Theorem: "If one of the angles in a triangle is a right angle, then the sum of the squares of the adjacent sides is equal to the square of the opposite side."
There are two key ideas in the reductio line of reasoning. First, a proposition must either be true or false, but not both. Therefore, if it cannot possibly be false, then it must be true. This is as simple as it is essential. Second, if a formally correct derivation from a set of assumptions leads to a contradiction, then at least one assumption must be false.
reductio ad absurdum is Latin, and means reduction to an absurdity. That describes the proof technique quite well: Start with a particular assumption, and show that your assumption leads to something absurd - a contradiction. Let p be the proposition to be proved. The key step is to assume that p is false, i.e., that not-p is true. Then, using rules of inference, derive some consequences of not-p. If not-p leads to a contradiction, then the original assumption "not-p is true" must be false. So p must be true, which is just what you set out to prove.
An example from number theory illustrates this proof strategy nicely. Consider the conditional statement (p):
"If a2 is an even number, then a must also be an even number."
Suppose this statement were false. Then it would be possible that for some odd integer a, a2 is even. In formal language, we assume the negation of p which amounts to:
"a2 is even and a is odd."
Now, a2 = a x a. This means that a2 is the product of two odd numbers (a, and again, a). But it is a simple fact of number theory that the product of two odd numbers must also be odd. This contradicts the hypothesis that a2 is even. Our assumption (not-p) must be false, so p must be true, finishing the proof.
When proving a conditional statement in mathematics, the easiest thing to do is usually to start off on a reductio proof. Quite often, this is the quickest way to demonstrate the desired conclusion.
This is the complete article, containing 408 words
(approx. 1 page at 300 words per page).
