Proof by contrapositive is a technique based on the logical equivalence \(p \implies q \equiv (\lnot q) \implies (\lnot p)\text{.}\) To show \(p \implies q\) is true, we can show \((\lnot q) \implies (\lnot p)\) directly. Our strategy becomes
Assume \((\lnot q)\) is true (equivalently, assume \(q\) is false).
Use this assumption (and definitions, theorems, or previous results) to show that \((\lnot p)\) must be true, too. (Equivalently, \(p\) must be false.)
Then, it follows that the truth value of the implication \(p \implies q\) is true.
Example3.2.1.
Claim. For all \(a \in \mathbb{Z}\text{,}\) if \(a^2\) is even, then \(a\) is even.
Proof.
Let \(a \in \mathbb{Z}\text{.}\) Assume \(a\) is not even; this means that \(a\) is odd. Thus there exists an integer \(k\) for which \(a = 2k + 1\text{.}\) It follows that \(a^2 = 2(2k^2+2k) + 1\text{.}\) Since \(2k^2+2k \in \mathbb{Z}\text{,}\) we see that \(a^2\) is odd and therefore not even.
Subsection3.2.2Proof by Contradiction
In a proof by contradiction, we show the statement \(p \implies q\) is true by showing it cannot possibly be false (we’re really invoking the Law of the Excluded Middle here). In other words, we assume that the entire implication is false, and then we show that this contradicts some other known result.
Remember that an implication is false exactly when the hypothesis is true and the conclusion is false. That is, by the Law of Implication (b), \(\lnot(p \implies q) \equiv p \land (\lnot q)\text{.}\)
Example3.2.2.
Claim. For all real numbers \(x\text{,}\) if \(x^2 = 2\text{,}\) then \(x\) is irrational. (Recall that a number \(x\) is rational provided there exist integers \(m\) and \(n \not = 0\) sharing no common factor such that \(x = \frac{m}{n}\text{.}\))
Proof.
Let \(x \in \mathbb{R}\text{.}\) Seeking a contradiction, assume \(x^2 = 2\) and \(x\) is rational. Then by definition of rational, \(x = \frac{m}{n}\) for some \(m,n \in \ZZ\) (\(n \not = 0\)) having no common factors. By assumpition, \(x^2 = \frac{m^2}{n^2} = 2\text{,}\) which implies that \(m^2 = 2n^2\text{.}\) By Example (referenvce), we see that \(m\) is even. That is, there exists \(k \in \mathbb{Z}\) such that \(m = 2k\text{.}\) Then \(m^2 = 2(2k^2) = 2n^2\text{,}\) so \(n^2 = 2k^2\text{.}\) By Example (ref), we have that \(n\) is even, too. So there exists \(\ell \in \mathbb{Z}\) such that \(n = 2 \ell\text{.}\) But now \(m\) and \(n\) share a common factor of \(2\text{,}\) and this is a contradiction.
Subsection3.2.3Other Logical Equivalences
As our implications become more complicated, like \(p \implies (q \lor r)\text{,}\) we will develop logical equivalences to make these statements easier to prove. Often this means moving the implication symbol as far to the right as possible so that we can assume as much as possible. Then, prove the new implication directly.
Having established in a previous exercise that \((p \implies (q \lor r)) \equiv (p \land (\lnot q))\implies r\text{,}\) we can use this equivalence to prove the following statement.
Example3.2.3.
Claim. For all integers \(a\) and \(b\text{,}\) if \(ab\) is even, then \(a\) or \(b\) is even.
Proof.
Let \(a\) and \(b\) be integers. Assume the product \(ab\) is even but \(a\) is not even. This means that there exist integers \(n\) and \(m\) for which \(ab = 2n\) and \(a = 2m+1\text{.}\) It follows that \(2n = (2m+1)b = 2mb + b\text{,}\) and isolating \(b\text{,}\) we find \(b = 2(n-mb)\text{.}\) Since \(n-mb\) is an integer, it follows that \(b\) is even.
