Contradiction

Another important proof strategy is called proof by contradiction. In particular, we assume that the statement we want to prove is false, and use logical deductions to derive something which is trivially false (e.g., $0 \neq 0$). This would then imply that the original statement must be true. Let’s again look at a concrete and classical example. We say that a positive integer $x$ is a prime if $1$ and $x$ are the only positive integers that divide $x$. We will use the following lemma (whose proof is deferred to the subsequent lectures).

Lemma 1

Every integer greater than $1$ has a prime divisor.

Example 12 (Infinitude of primes)

We want to prove that there are infinitely many primes. Let us start by assuming that this statement is false, so we can list the primes as $p_1, \ldots , p_n$. Now we can define $x = p_1 \cdot p_2 \cdot \ldots \cdot p_n + 1$. This number is greater than every (assumed) prime, so this is not a prime. By Lemma 1, there is a prime $p_i$ that divides $x$. Since $p_i$ divides $x$ and also divides $p_1 \cdot p_2 \cdot \ldots \cdot p_n$, we have that $p_i | (x - p_1 \cdot p_2 \cdot \ldots \cdot p_n) = 1$, so $p_i \le 1$, a contradiction.

Example 13

$\sqrt{2}$ is irrational. To prove this assume that $a = \sqrt{2}$ is rational ($a = p/q$ for integers $p$ and $q$ that have no common factor). By squaring both sides, we have that $p^2 = 2q^2$ , and thus $p^2$ is even. Applying Exercise 1, we know that $p$ must be even, so $p = 2k$ for some integer $k$. Plugging this in, we have $4k^2 = 2q^2$ or $2k^2 = q^2$ , and thus $q^2$ is even. Again, from Exercise 1, we have that $q$ is even, so $2$ is a common factor of $p$ and $q$, a contradiction.

Again, in this proof strategy, it would seem like we have no way to know in advance which contradiction we are looking for. In general, what people do is to keep deriving more facts/information about the problem, and hopefully the contradiction would reveal itself at some point. Of course, once you gain more experience, this thing becomes more systematic and gets easier.