Contraposition

The contraposition of the statement $P \Rightarrow Q$ is $\neg Q \Rightarrow \neg P$. Despite being equivalent, we will often find that one statement is easier to prove than another. Let us look at some concrete examples. We say that $a \equiv b \pmod{m}$ ("$a$ is congruent to $b$ modulo $m$") if $m \mid (a - b)$. For example, $12 \equiv 18 \pmod{-3}$ and $3 \equiv -4 \pmod{7}$. Notice, $x \equiv 1 \pmod{2}$ for odd integer $x$.

Example 9

For all integers $a, b$ where $a \mid b$, if $b$ is odd, then $a$ is odd. Try to prove this by a direct proof, and you will see that it is a bit confusing. On the other hand, if we prove the contrapositive, it is entirely trivial: Assume that $a$ is even, so $a = 2k$ for some $k \in \mathbb{Z}$. Since $a$ divides $b$, we have $b = q \cdot 2k = 2(kq)$ for some $q \in \mathbb{Z}$. This implies that $b$ is also even.

Example 10

Prove: $(\forall x)[(\forall y)(x \mid y) \Rightarrow x = \pm 1]$. This can be read in English as "an integer $x$ that divides every integer must be $+1$ or $-1$". So the contraposition is $(\forall x)[x \neq \pm 1 \Rightarrow (\exists y)(x \not\mid y)]$. To prove this, assume that we have integer $x \neq \pm 1$. Notice that $x \not\mid 1$ (and integer $1$ serves as our $y$).

Example 11 (Pigeonhole's principle)

Let $n$ and $k$ be positive integers. Place $n$ objects into $k$ boxes. If $n > k$, then at least one box contains more than one object. To prove this, assume that each box contains at most one object. This implies that the total number of objects is at most the number of boxes $(n \le k)$.

From these examples, it may seem like there is no way to tell in advance whether the direct statement or its contraposition would be easier to prove. Indeed, this is something that you would pick up on once you get used to them (which we hope would happen to everyone before the end of this course).

Exercise 1

Let $x$ be an integer. If $x^2$ is even, then $x$ is even.