Proof by Contrapositive

Fact: \(P(x) \implies Q(x) \iff \left[ \neg Q(x) \implies \neg P(x)\right]\)

Proof:

This results in a proof technique called proof by contrapositive.

Result 3.10: let \(x \in \mathbb{Z}\). If \(5x-7\) is even, then \(x\) is odd.

Proof (Contrapositive):

• Assume \(x\) is even, so \(x = 2k, k \in \mathbb{Z}\).
• We want to show that given \(x\) is even, then \(5x-7\) is odd (\(5x-7 = 2n+1, n \in \mathbb{Z}\)).
• Observe: \[ \begin{align} 5x-7 &= 5(2k)-7\\ &= 2(5k)-8 + 1\\ &= 2(5k-4) + 1 \end{align} \]
• So, \(5x-7\) is odd. \(\blacksquare\)

The contrapositive is often used when the hypothesis is difficult, but the conclusion is relatively simple.

Words of Conclusion

So, thus, therefore, hence, whence, thence, then, it follows that, we have, ...

Result: let \(x \in \mathbb{Z}\). \[ x -7 \text{ is even} \iff x \text{ is odd.} \]

Proof:

• Assume \(x\) is odd. Then \(x = 2k+1, k \in \mathbb{Z}\).
• We want to show that \(11x-7 = 2a, a \in \mathbb{Z}\).
• Observe: \[ \begin{align} 11x - 7 &= 11(2k+1) - 7\\ &= 2(11k+11) + 11 - 7\\ &= 2(11k) + 4\\ &= 2(11k+2)\\ \end{align} \]
• So \(11x-7\) is even.

For the forward direction, we'll prove by contrapositive.

• Assume \(x\) is even, so \(x = 2k, k \in \mathbb{Z}\).
• We want to show that \(11x-7 = 2a+1, a \in \mathbb{Z}\).
• Observe: \[ \begin{align} 11x-7 &= 11(2k)-7\\ &= 2(11k) - 8 + 1\\ &= 2(11k-4)+1 \end{align} \]
• So, \(11x-7\) is odd. \(\blacksquare\)

Theorem 3.12

• Let \(x \in \mathbb{Z}\). \(x^2\) is even \(\iff x\) is even.

Proof

• Assume \(x\) is even. In other words, \(x = 2k, k \in \mathbb{Z}\).
• We want to show that \(x^2 = 2a, a \in \mathbb{Z}\).
• Observe: \[ x^2 = (2k)^2 = 2(2k^2) \]
• We'll prove the forward direction by contrapositive.
• Assume \(x\) is odd. In other words, \(x = 2k+1, k \in \mathbb{Z}\).
• We want to show that \(x^2 = 2a + 1, a \in \mathbb{Z}\).
• Observe: \[ \begin{align} x^2 &= (2k+1)^2\\ &= 4k^2+4k+1\\ &= 2(2k^2+2k)+1 \end{align} \]
• So, \(x^2\) is odd. \(\blacksquare\)

What about \(x^2\) is odd \(\iff x\) is odd? We just proved that too!

Result to prove: let \(x \in \mathbb{Z}\). If \(5x-7\) is odd, then \(9x+2\) is even.

• Neither a direct proof nor a contrapositive proof seems useful, or at least neither seem like a clean approach.
• Technique: Introduce a lemma.
  • A lemma helps bridge the gap between hypothesis and conclusion.
  • A lemma is a separate result on its own!

Lemma: let \(x \in \mathbb{Z}\).

• if \(5x-7\) is odd, then \(x\) is even. (invented hypothesis to simplify)
• We'll prove by contrapositive.
• Assume \(x\) is odd, so \(x = 2k+1, k \in \mathbb{Z}\).
• We want to show that \(5x-7 = 2a, a \in \mathbb{Z}\).
• Observe: \[ \begin{align} 5x-7 &= 5(2k+1) - 7\\ &= 2(5k)+5 - 7\\ &= 2(5k) - 2\\ &= 2(5k-1) \end{align} \]
• So, \(5x-7\) is even. \(\blacksquare\)

Result 3.14: let \(x \in \mathbb{Z}\).

• If \(5x-7\) is odd, then \(9x+2\) is even.

Proof: Assume \(5x-7\) is odd. By the above lemma, \(x\) is even.

• So \(x = 2k, k \in \mathbb{Z}\).
• We want to show that \(9x+2 = 2a, a \in \mathbb{Z}\).
• Observe:

\[ \begin{align} 9x + 2 &= 9(2k)+2\\ &= 2(9k+1) \end{align} \]

• So, \(9x+2\) is even. \(\blacksquare\)