Proof by Contraposition
Equivalence of \(p\rightarrow q\) and its Contrapositive
Let \(p\) and \(q\) be statements. Recall that the statement \(p\rightarrow q\) is equivalent to its contrapositive \(\neg q \rightarrow \neg p\). This is shown to be true in the truth table below.
| \(p\) | \(q\) | \(\neg p\) | \(\neg q\) | \(p\rightarrow q\) | \(\neg q \rightarrow \neg p\) |
| F | F | T | T | T | T |
| F | T | T | F | T | T |
| T | F | F | T | F | F |
| T | T | F | F | T | T |
Proving Statements by Contraposition
Using the fact that an implication is logically equivalent to it’s contrapositive gives us a new proof technique that is convenient on certain occasions.
Let’s first see what happens when we try to prove this directly, as usual.
Proof: Suppose \(n^2\) is even. (Want to show \(n\) is even; i.e. \(n=2m\) for some integer \(m\).) Since \(n^2\) is even, \(n^2=2k\) for some integer \(k\). Then, taking square roots of both sides gives us \(n=\sqrt{2k}=\sqrt{2}\sqrt{k}\)…
But here we get stuck because \(\sqrt{2}\) is an ugly decimal (and therefore not even), and all we know about \(k\) is that it is some integer and not much else. We can’t even make additional assumptions about \(k\) to give us more information about \(k\) (such as assuming that \(k\) is odd or even, proving that the result holds in either case). So, effectively the proof we started above is useless due to the sheer lack of info.
Lets try this by contraposition. That is, lets prove the statement “If \(n\) is NOT even, then \(n^2\) is NOT even”
Proof: (Proof by contraposition) Suppose that \(n\) is NOT even; i.e. that \(n\) is odd. (We want to show that \(n^2\) is odd; i.e. \(n^2=2m+1\) for some integer \(m\).) Since \(n\) is assumed to be odd, \(n=2k+1\) for some integer \(k\). Then, notice
$$\begin{align} n^2&=(2k+1)^2\\&=(2k+1)(2k+1)\\&=(4k^2+4k+1)\\&=2(2k^2+2k)+1\end{align}$$
Note that \(2k^2+2k\) is an integer (because products and sums of integers are integers). Therefore, we have \(n^2=2m+1\) for some integer \(m\), which proves that \(n^2\) is odd (i.e. NOT even). But this was exactly what we wanted to show. QED.
Note that if we start by trying to prove this directly, we would assume that \(n\not| ab\), but all this really gives us is the fact “for every integer \(m\), \(ab\neq n\cdot m\)” by definition of divides. But since we don’t have an equality, this makes this fact hard (if not impossible) to work with algebraically (how does one algebraically manipulate non-equations?) It would be much easier to work with equalities, which is exactly what the contrapositive would give us.
Contrapositive of the original statement: “If \(n\vert a\) OR \(n\vert b\), then \(n\vert ab\)”
(Note: to find the negation of the conclusion statement “\(n\not| a\) and \(n\not| b\)” we used De Morgan’s Laws.)
Proof: Let \(n,a,b\) be integers. Assume that \(n\vert a\) OR \(n\vert b\) is true. (Want to show in either case that \(n\vert ab\); i.e. \(ab=n\cdot m\) for some integer \(m\).)
Lets assume that \(n\vert a\) first. Then, \(a=nk\) for some integer \(k\). Then, \(ab=(nk)b\) by substituting in \(nk\) for \(a\). Therefore, we have \(ab=n(kb)\) and \(kb\) is clearly an integer. Thus, we have shown \(n\vert ab\) if we assume \(n\vert a\).
Now, lets assume \(n\vert b\). Then, \(b=nq\) for some integer \(q\). Then, \(ab=a(nq)\) by substituting in \(nq\) for \(b\). Therefore, by rearranging factors, we have \(ab=n(aq)\) and \(aq\) is clearly an integer. Thus, we have shown \(n\vert ab\) if we assume \(n\vert b\).
Therefore, by the last two paragraphs, we have shown that \(n\vert ab\) if \(n\vert a\) OR \(n\vert b\), which is exactly what we wanted to show.
“If \(n\) is even, then \(5n+2\) is even.”
Proof: Suppose \(n\) is even. (Want to show that \(5n+2\) is even). Then, since \(n\) is assumed to be even, \(n=2m\) for some integer \(m\). Now, notice that
\begin{align}5n+2&=5(2m)+2\\&=5\cdot 2\cdot m +2\\&=2(5m+1)\end{align}
Since \(5m+1\) is an integer, and since \(5n+2=2(5m+1)\) it follows that \(5n+2\) is even, which is exactly what we wanted to prove.
Therefore, we have proved the original statement “If \(5n+2\) is odd then, \(n\) is odd.” true by contraposition. QED
The original statement could have been proved directly with a little algebra on the equation one gets by assuming the original statement’s hypothesis.
“If \(p\leq 100\) and \(q\leq 100\), then \(p\cdot q \leq 10000\).”
Proof: Suppose that \(p\leq 100\) and \(q\leq 100\). We want to show that \(pq\leq 10000\). So, note that multiplying the inequality \(p\leq 100\) on both sides by \(q\) gives us \(pq\leq 100q\). Note also that multiplying both sides of \(q\leq 100\) by \(100\) gives us that \(100q\leq 10000\). Putting these inequalities together, we have that
$$\begin{align} pq\leq 100q\leq 10000\end{align}$$
Therefore, we have \(pq\leq 10000\), which is exactly what we wished to show. Thus, by contraposition, the original statement “If \(p\cdot q>10000\), then \(p>100\) or \(q>100\)” is true.
Note that in the original statement, we would have needed to assume “\(p\cdot q >10000\)” and then prove “\(p>100\) or \(q>100\).” Assuming “\(p\cdot q >10000\)” gives us next to nothing to work with. The best you can (probably) do here is divide both sides by, say, \(q\) which gives us \(p>\frac{10000}{q}\), but knowing nothing about \(q\) aside from the fact that it is prime (which isn’t helpful) we can’t really do anything else, unless you feel like checking the inequality for lots of pairs of primes \(p\) and \(q\). Proof by contrapositive makes perfect sense in this case, since assuming “\(p\leq 100\) and \(q\leq 100\)” gives us a LOT to work with.
Recall that a rational number is any number that can be written as a fraction of integers. The set of all rational numbers is denoted \(\mathbb{Q}\). So, if \(n\in\mathbb{Q}\), then by this definition, there are integers \(p,q\) such that \(n=\frac{p}{q}\).
“If \(p\) is rational AND \(q\) is rational, then the product \(p\cdot q\) is rational.”
Proof: Suppose that \(p\) and \(q\) are rational numbers. Then \(p=\frac{n_0}{m_0}\) and \(q=\frac{n_1}{m_1}\) for some integers \(n_0,n_1,m_0,m_1\). Then, notice that
$$\begin{align}p\cdot q&=\left(\frac{n_0}{m_0}\right)\left(\frac{n_1}{m_1}\right)\\&=\frac{n_0n_1}{m_0m_1}\end{align}$$
Since \(n_0n_1\) and \(m_0m_1\) are clearly integers (products of integers are integers), and by the above equation, it follows that \(p\cdot q\) is a rational number (by definition of rational numbers), which is exactly what we were trying to prove.
Therefore, we have shown that “If the product \(pq\) is irrational, then \(p\) is irrational, or \(q\) is irrational” is true by contraposition.
Note that in the original statement, assuming “\(pq\) is irrational” gives us nothing to work with. While we can say “\(pq\neq\frac{n}{m}\) for integers \(n\) and \(m\)” we can’t do much with a “non-equation.”