1.8: Proof by Contradiction

In a proof by contradiction, or indirect proof, you show that if a proposition were false, then some false fact would be true. Since a false fact by definition can’t be true, the proposition must be true.

Proof by contradiction is always a viable approach. However, as the name suggests, indirect proofs can be a little convoluted, so direct proofs are generally preferable when they are available.

Method: In order to prove a proposition \(P\) by contradiction:

1. Write, “We use proof by contradiction.”
2. Write, “Suppose \(P\) is false.”
3. Deduce something known to be false (a logical contradiction).
4. Write, “This is a contradiction. Therefore, \(P\) must be true.”

Example

We’ll prove by contradiction that \(\sqrt{2}\) is irrational. Remember that a number is rational if it is equal to a ratio of integers—for example, \(3.5 = 7/2\) and \(0.1111 \cdots = 1/9\) are rational numbers.

Theorem \(\PageIndex{1}\)

\(\sqrt{2}\) is irrational.

Proof

We use proof by contradiction. Suppose the claim is false, and \(\sqrt{2}\) is rational. Then we can write \(\sqrt{2}\) as a fraction \(n/d\) in lowest terms.

Squaring both sides gives \(2 = n^2 / d^2\)and so \(2d^2 = n^2\). This implies that n is a multiple of 2 (see Problems 1.10 and 1.11). Therefore \(n^2\) must be a multiple of 4. But since \(2d^2 = n^2\), we know \(2d^2\) is a multiple of 4 and so \(d^2\) is a multiple of 2. This implies that \(d\) is a multiple of 2.

So, the numerator and denominator have 2 as a common factor, which contradicts the fact that \(n/d\) is in lowest terms. Thus, \(\sqrt{2}\) must be irrational. \(\quad \blacksquare\)