Proof by Contradiction

To prove a statement P by contradiction, you assume the negation $\lnot P$ of what you want to prove and try to derive a contradiction (usually a statement of the form $A \land \lnot A$ ). Since a contradiction is always false, your assumption $\lnot P$ must be false, so the original statement P must be true.

Example. Prove: A \hskip0.5in Premises: $\left\{\matrix{(\lnot B \lor C) \ifthen A \cr B \ifthen D \cr C \lor \lnot D \cr}\right.$

Since I want to prove A by contradiction, I begin by assuming the negation $\lnot A$ . I'm trying to construct a contradiction of the form $\hbox{FOO} \land \lnot\hbox{FOO}$ .

1. $\lnot A$ Premise for proof by contradiction
2. $(\lnot B \lor C) \ifthen A$ Premise
3. $\lnot(\lnot B \lor C)$ Modus tollens (1,2)
4. $B \land \lnot C$ DeMorgan (3)
5. B Decomposing a conjunction (4)
6. $\lnot C$ Decomposing a conjunction (4)
7. $B \ifthen D$ Premise
8. D Modus ponens (5.7)
9. $C \lor \lnot D$ Premise
10. C Disjunctive syllogism (8,9)
11. $C \land \lnot C$ Constructing a conjunction (6,10)
12. A Proof by contradiction (1,11)

I arrived at the contradiction $C \land \lnot C$ at line 11. Therefore, I conclude that my premise $\lnot A$ was false, so A must be true (line 12).

The next two proofs are very well-known: Everyone who studies math sees them sooner or later. The first is Euclid's proof that there are infinitely many prime numbers; it occurs in Book IX of Euclid's Elements, which was composed around 300 B.C. and is arguably the most famous math textbook of all time.

The second proves that $\sqrt{2}$ is irrational. The discovery that there are quantities which can't be expressed in terms of whole numbers or their ratios was known to the ancient Greeks; Boyer and Mertzbach [1] place the discovery prior to 410 B.C.

Example. Prove that there are infinitely many prime numbers. (An integer $n > 1$ is prime if its only positive divisors are 1 and n.)

Suppose that there are not infinitely many prime numbers. That means there are finitely many prime numbers --- suppose they are

$$p_1, \quad p_2, \quad \ldots, \quad p_n.$$

Look at the number

$$x = p_1p_2 \cdots p_n + 1.$$

(It's the product of all of the p's, plus one. Notice that the product of the p's wouldn't make sense if there were infinitely many p's.)

x leaves a remainder of 1 when it's divided by $p_1$ , since $p_1$ divides evenly into the $p_1p_2 \cdots p_n$ term. Likewise, x leaves a remainder of 1 when it's divided by $p_2$ , ..., $p_n$ . Therefore, x is not divisible by any of the p's --- that is, x is not divisible by any prime number.

However, every integer greater than 1 is divisible by some prime number. A precise proof of this fact requires induction, which I'll discuss later. But you can see that it's reasonable. If a number z is prime, it's divisible by a prime, namely z. Otherwise, you can factor z into a product of two smaller numbers. If either factor is prime, then the prime factor is a prime which divides z. If neither factor of z is prime, you can factor them, and so on. Eventually, the process must stop, because the factors always get smaller.

Returning to my proof, I've found that x isn't divisible by any prime number, which I've just noted is impossible. This contradiction shows that there must be infinitely many prime numbers.

Example. $\sqrt{2}$ is irrational. (A rational number is a real number which can be written in the form $\dfrac{m}{n}$ , where m and n are integers. A real number which is not rational is irrational.)

Suppose on the contrary that $\sqrt{2}$ is rational. Then I can write $\sqrt{2} = \dfrac{m}{n}$ , where $m, n \in \integer$ . (Remember that $\integer$ stands for the set of integers.) By dividing out any common factors, I can assume that $\dfrac{m}{n}$ is in lowest terms (that is, m and n have no common factors besides 1 and -1).

Clear the denominator, then square both sides:

$$\sqrt{2}n = m, \quad 2n^2 = m^2.$$

Since 2 divides the left side, it must divide the right side. But if 2 divides $m^2$ , it must in fact divide m. So suppose $m = 2k$ , where $k \in \integer$ . Substitute in the previous equation and cancel a factor of 2:

$$2n^2 = (2k)^2 = 4k^2, \quad n^2 = 2k^2.$$

Now 2 divides the right side, so it must divide the left side. But if 2 divides $n^2$ , it must divide n.

However, I already showed that 2 divides m, so 2 divides both m and n. This contradicts my assumption that the fraction $\dfrac{m}{n}$ was in lowest terms.

Therefore, $\sqrt{2}$ must be irrational.

The preceding examples give situations in which proof by contradiction might be useful:

Having said this, I should note that it is considered bad style to write a proof by contradiction when you can give a direct proof. In those situations, the proof by contradiction often looks awkward. Moreover, the direct proof will often tell you more. For example, a direct proof that something exists will often work by constructing the object. This is better than simply knowing that the object exists on logical grounds.

In some cases, proof by contradiction is used as part of a larger proof --- for instance, to eliminate certain possibilities.

Example. Prove that the function $f(x) = x^5 + 6x^3 + 17x + 1$ cannot have more than one root.

In this proof, I'll use Rolle's Theorem, which says: If f is continuous on the interval $[a, b]$ , differentiable on the interval $(a, b)$ , and $f(a) = f(b)$ , then $f'(c) = 0$ for some $c \in (a, b)$ .

Suppose on the contrary that $f(x) = x^5 + 6x^3 + 17x + 1$ has more than one root. Then f has at least two roots. Suppose that a and b are (different) roots of f with $a < b$ .

Since f is a polynomial, it is continuous and differentiable for all x. Since a and b are roots, I have

$$f(a) = 0 \quad\hbox{and}\quad f(b) = 0, \quad\hbox{so}\quad f(a) = f(b).$$

By Rolle's Theorem, $f'(c) = 0$ for some c such that $a < c < b$ .

However,

$$f'(x) = 5x^4 + 18x^2 + 17.$$

Since $f'(x)$ is a sum of even powers and a positive number (17), it follows that $f'(x) > 0$ for all x. This contradicts $f'(c) = 0$ .

Therefore, f does not have more than one root.

Note: You could use the Intermediate Value Theorem to show that $f(x)$ has at least one root. Combined with the result I just proved, this shows that $f(x)$ has exactly one root.

Example. On a certain island, each inhabitant always lies or always tells the truth. Calvin and Phoebe live on the island.

Calvin says: "Exactly one of us is lying."

Phoebe says: "Calvin is telling the truth."

Determine who is telling the truth and who is lying.

Suppose Calvin is a truth teller. Then "Exactly one of us is lying" is true, and since Calvin is a truth teller, Phoebe is a liar. Therefore, "Calvin is telling the truth" is a lie, so Calvin must be lying. This is a contradiction, because I assumed he was telling the truth.

Hence, I've proved by contradiction that Calvin must be a liar. Hence, "Exactly one of us is lying" is false. This gives two possibilities: Either both are telling the truth, or both are lying.

Suppose both are telling the truth. This contradicts the established fact that Calvin is lying.

The only other possibility is that both are lying. Then Calvin's statement "Exactly one of us is lying" should be false (and it is), and Phoebe's statement "Calvin is telling the truth" should be false (and it is). Thus, this is the only possibility, and it's consistent with the given statements.

Therefore, Calvin and Phoebe are both liars.

[1] Carl Boyer, A History of Mathematics (2$^{\rm nd}$ edition) (revised by Uta Merzbach), New York: John Wiley \& Sons, Inc., 1991.

Send comments about this page to: Bruce.Ikenaga@millersville.edu.

Bruce Ikenaga's Home Page

Copyright 2008 by Bruce Ikenaga