| | |
An indirect argument, otherwise known as a proof by contradiction, is a twist on a proof by cases and is an especially powerful way to prove statements which are negations of other statements.
Let us consider the overall strategy behind this technique before turning our attention to specific examples:
Suppose one wishes to prove some statement $S$. Certainly one must acknowledge that one of two cases must occur: Either $S$ is true or it is not true. An indirect argument hopes to argue that the second case (i.e., $S$ is not true) leads to a clear contradiction of something known to be true, and thus can't be possible. That leaves only the possibility of the case where $S$ is true, completing the argument.
$$ \begin{array}{l} \textrm{Case 1: } \, S \textrm{ is true } \\ \textrm{Case 2: } \, S \textrm{ is not true } \implies \cdots \implies \textrm{ a contradiction! (so this case never happens)} \end{array} $$In practice, we shorten this to assuming the opposite of what we wish to show is true (i.e., $S$ is not true), and try to argue to a contradiction. Upon reaching the contradiction we have proven what we wished to show true.
As a more specific example, consider the proof that for any integer $n$, if $2 \mid n^2$ then $2 \mid n$, discussed below:
To argue this indirectly, we assume the opposite of that what we hope to show. In other words, suppose $2 \not \mid n$. Then $n$ must be odd, and can be written as $n = 2k+1$ for some integer $k$. But then, $$\begin{split} n^2 &= (2k+1)^2\\ &= 4k^2 + 4k + 1\\ &= 2(2k^2 + 2k) + 1 \end{split}$$ Letting $m = 2k^2 + 2k$, and noting that $m \in \mathbb{Z}$ by closure, we know $n^2 = 2m + 1$ for some integer $m$. Consequently, since it is clear that dividing $n^2$ by $2$ leaves a nonzero remainder, it must be the case that $2 \not \mid n^2$.
However, this contradicts the stated hypothesis that $2 \mid n^2$.
Thus, we reject our assumption that $2 \not \mid n$, which leaves $2 \mid n$ as the only possibility. This, of course, is what we hoped to show.
As a second example (and a classic one at that) suppose one wishes to prove that there are an infinite number of primes. This proof -- argued by Euclid over 2400 years ago -- requires a little more creativity than our first example, but the result is well worth it!
We again assume the opposite of what we are trying to show. In this case, that means we assume that there are only a finite number of primes.
Under this assumption, we can let $n$ denote the number of primes, and list them all in the following way: $$p_1, p_2, p_3, \ldots, p_n$$ Now consider the number $$q = p_1 p_2 p_3 \ldots p_n + 1$$ Clearly, $q$ is larger than the largest prime, so it can't be prime itself. Thus, some prime must divide $q$. Without loss of generality, suppose $p_1 \mid q$. But then, $$\begin{align*}p_1 \mid p_1 p_2 p_3 \ldots p_n + 1 &\implies p_1 p_2 p_3 \ldots p_n + 1 = p_1 k \quad \textrm{for some integer $k$}\\ &\implies 1 = p_1 k - p_1 p_2 p_3 \ldots p_n\\ &\implies 1 = p_1(k - p_2 p_3 \ldots p_n)\\ &\implies p_1 \mid 1\end{align*}$$ But no prime can divide 1! This gives us the contradiction we need.
Our assumption must be rejected, and the opposite must be true:
There are infinitely many primes.†
† Note that the argument used to prove this, as shown above, relies on the fact that every integer greater than one has a prime divisor. While this is certainly true -- there is more to why this is true than some will realize. Stay tuned, though -- all will eventually be revealed! :)