Proof by contradiction establishes the truth of a statement by showing that assuming that the statement to be false leads to a contradiction.

To prove something by contradiction:

1. Assume that the statement is not true.
2. Show that the consequences of this assumption leads to an impossible result.

You must be able to prove the following:

• Prove by contradiction that $\sqrt{2}$ is irrational.
• Prove by contradiction that the number of prime numbers is infinite.

Example 1

Prove by contradiction that $\sqrt{2}$ is irrational.

Assume that $\sqrt{2}$ is rational. Then there exist integers $a$ and $b$ with $b \neq 0$ such that $\sqrt{2} = \frac{a}{b}$, where the fraction is in lowest terms (i.e., $a$ and $b$ have no common factor greater than 1).

Squaring both sides gives $2 = \frac{a^2}{b^2}$, so $a^2 = 2b^2$. This implies that $a^2$ is even, and therefore $a$ must be even (since the square of an odd number is odd).

Write $a = 2c$ for some integer $c$. Substituting into $a^2 = 2b^2$ yields $(2c)^2 = 2b^2$, i.e., $4c^2 = 2b^2$, so $2c^2 = b^2$. Hence $b^2$ is even, and consequently $b$ is even.

Thus both $a$ and $b$ are even, meaning they have a common factor of $2$. This contradicts the assumption that $\frac{a}{b}$ was in lowest terms.

Therefore our initial assumption is false, and $\sqrt{2}$ must be irrational.

Example 2

Prove by contradiction that the number of prime numbers is infinite.

Assume that there is a finite number of prime numbers. Then we can list them as $p_1, p_2, p_3, \dots, p_n$, where $n$ is some positive integer.

Now consider the number

$$N = p_1 p_2 p_3 \dots p_n + 1.$$

There are two cases for $N$:

If $N$ is prime, then $N$ is a prime number not in our original list (since it is larger than any $p_i$), contradicting the assumption that we had listed all primes.

If $N$ is composite, then it must have a prime divisor $q$. But $q$ can't be one of the primes $p_1, p_2, \dots, p_n$, because N dividing by any of $p_1, p_2, \dots, p_n$ would leave a remainder of 1. Therefore $q$ must be a prime not in our original list.

In either case, we have found a prime not among $p_1, p_2, \dots, p_n$, contradicting the assumption that the list contained all primes.

Hence the assumption is false, and there must be infinitely many prime numbers.