Basics: Proof by Contradiction

Proofs by contradiction are also known as "Reducto Ad Absurdum." Conceptually, they are very simple and elegant proofs. They lie on the premise that something must be either true or false. If you want to prove something true then assume it is false. If making it false gives you nonsensical, contradictory conclusions then it must be true. It is important to note, however, that not all schools of mathematics consider proofs by contradictions legitimate proofs.

More formally, we can give the essence of the proof as such: for any statement S, S or !S (not S) must be true. There is no middle ground. If we can show that !S leads to an absurd result then S must be true. We can also work in reverse. To show that !S is true, we assume that S is true. If S leads to nonsensical results then !S must be true.

Using a proof by contradiction, it can be shown that √2 is an irrational number. For those that don't know, a rational number can be expressed as the ratio of two integers: a/b. An irrational number can not be expressed as a ratio of two integers. Pi, Euler's number (e), and √2 are all irrational numbers. Here we will look at the proof of the irrationality of the √2.

1. Assume that √2 is a rational number, meaning that there exists an integer a and an integer b such that a / b = √2.

2. Then √2 can be written as an irreducible fraction a / b such that a and b are coprime integers and (a / b)² = 2.

3. It follows that a² / b² = 2 and a² = 2 b²

4. Therefore a² is even because it is equal to 2 b². (2 b² is logically necessarily even because it's divisible by 2—that is, (2 b²)/2 = b²—and numbers divisible by two are even by definition.)

5. It follows that a must be even as only even numbers have even squares.

6. Because a is even, there exists an integer k that fulfills: a = 2k.

7. Substituting 2k from (6) for a in the second equation of (3): 2b² = (2k)² is equivalent to 2b² = 4k² is equivalent to b² = 2k².

8. Because 2k² is divisible by two and therefore even, and because 2k² = b², it follows that b² is also even which means that b is even.

9. By (5) and (8) a and b are both even, which contradicts that a / b is irreducible as stated in (2). [1]

So we see that by assuming that the square-root of 2 is even we arrive at a contradictory conclusion. Q.E.D.

We can also use the proof by contradiction to show the error in a faulty syllogism. A syllogism is a kind of argument where one proposition is inferred from two others. [2] For instance, if we are given that all A are B, and that all B are C then we can conclude that all A are C. People often make the mistake of concluding that all C are A. We can use the proof by contradiction to show that this assertion is false by assuming that it is true.

1.) All women are humans.

2.) All humans are mortals.

3.) Based on the conditions above, we can conclude that all mortals are women.

4.) However, many men are mortals as well. Therefore, our logic above is flawed, and the statement that all C are A (all mortals are women) is proved wrong. Q.E.D.

There are certain pitfalls to avoid in the proof by contradiction. For instance, you must be sure that the contradiction is a true contradiction. Many creationist arguments come from the proof by contradiction on the basis of things that seem unlikely. This not a contradiction. They must be logically impossible.

[1] http://en.wikipedia.org/wiki/Root_2
[2] http://en.wikipedia.org/wiki/Syllogism