Section 4.2 Indirect proofs
Many statements are difficult, or even impossible, to prove directly. In this chapter we will consider two methods of indirect proof: proof by contraposition and proof by contradiction.
Subsection 4.2.1 Proof by contraposition
Consider the following, the converse of the theorem we proved in the previous section.
Theorem 4.2.1.
If \(n\) is an integer such that \(n^2\) is even, then \(n\) is even.
This theorem claims that if we know an integer's square is even, then we can conclude the integer is even as well. This is the converse statement of saying that an even integer has an even square. What would happen if we tried to prove it directly? Well, since \(n^2\) is even, we could write \(n^2 = 2m\) for some integer \(m\text{.}\) Then since we want to talk about \(n\text{,}\) we could take square roots: \(n = \sqrt{2m}\) (if \(n\) is positive). But then what? We don't know anything about square roots of integers. In fact, square roots are pretty hard to work with.
Since it is easier to take powers than to take roots, it would be nice to “turn the arrow around”. We can do this by exploiting the fact, which we learned in the previous chapter, that the conditional statement \(p \to q\) is equivalent to its contrapositive \(\neg q \to \neg p\text{.}\) In this case, the statement “If \(n^2\) is even then so is \(n\)” is equivalent to the statement “If \(n\) is odd then so is \(n^2\text{.}\)”
Proof.
Let \(n\) be an integer. We will prove that if \(n\) is odd then \(n^2\) is odd, in order to prove the equivalent statement that if \(n^2\) is even then \(n\) is even.
Let \(n\) be odd, then, so that there exists an integer \(m\) where \(n = 2m+1\text{.}\) Therefore,
which is odd by definition. Thus if \(n^2\) is even then \(n\) must be even as well.
Take care in identifying whether a proof about parity or divisibility required the direct or indirect approach. If \(n\) is in the antecedent, the approach is likely direct. If the expression involving \(n\) is in the antecedent, the approach is likely indirect.
Example 4.2.2.
Prove that if \(n\) is an integer such that \(2n^2 + 3n - 2\) is odd, then \(n\) is odd.
Prove this indirectly using contraposition. In other words, prove that if \(n\) is even, that \(2n^2 + 3n - 2\) is even. Try it yourself before reading the following proof.
Proof.
Let \(n\) be an integer. We will prove that if \(2n^2 + 3n - 2\) is odd, then \(n\) is odd by proving the contrapositive. So, suppose that \(n\) is even. Therefore there exists an integer \(m\) such that \(n=2m\text{.}\)
When \(n\) is even, \(2n^2 + 3n - 2\) is even. Therefore if \(2n^2+3n-2\) is odd, then \(n\) must also be odd.
Subsection 4.2.2 Proof by contradiction
Another indirect proof technique, called proof by contradiction, relies on the law of the excluded middle. Recall that this is the law that \(\neg(\neg q) \equiv q\text{,}\) and some mathematicians do not believe in its validity. Therefore we present it here as a secondary technique (everyone agrees contraposition works).
Suppose you want to prove \(p \to q\text{.}\) You assume that \(p\) and \(\neg q\) are both true and derive some kind of impossibility. Therefore, you have shown \(p \to \neg(\neg q)\text{.}\) If \(\neg(\neg q) \equiv q\text{,}\) then you have shown \(p \to q\text{.}\) Let's prove that if \(n\) is an integer and \(n^2\) is even, then \(n\) is even using contradiction.
Proof.
Suppose that \(n\) is an integer where \(n^2\) is even but \(n\) is odd. Since \(n\) is odd, there exists an integer \(m\) such that \(n=2m+1\text{.}\) Then,
We have shown that \(n^2\) is odd despite our initial assumption that it is even. Since no integer can be simultaneously odd and even, if \(n^2\) is even and \(n\) is an integer, then \(n\) must also be even.
A famous proof by contradiction is the proof that \(\sqrt{2}\) is not a rational number.
Proof.
Suppose that \(\sqrt{2}\) is a rational number. By definition, there exist integers \(p\) and \(q\) such that \(q\neq 0\) and
Furthermore, we may freely assume this fraction is “in lowest terms”, meaning that \(p\) and \(q\) have no factors in common. Then,
so
Observe that this forces \(p\) to be even because we have proven that if \(p^2\) is even, then \(p\) is. Therefore \(q\) can't be even, because we assumed \(p/q\) to be in lowest terms. Thus, \(q\) is odd. Thus there exist integers \(k\) and \(m\) where \(p = 2k\) and \(q = 2m+1\text{.}\) We will show that we have inadvertantly proven that \(1\) is an even number.
As we know, \(1\) is not even. Therefore, \(q\) cannot be odd either. We are forced to conclude that there are no such integers \(p\) and \(q\) where \(\sqrt{2} = p/q\text{.}\) Hence, \(\sqrt{2}\) is irrational (not rational).