1.4b Proof by Contraposition

Proof by Contraposition

A proof by contraposition is a logical argument that establishes the truth of a given implication $P⟹Q$ by assuming the truth of the negation of the conclusion $\neg Q$, and demonstrating that the negation of the hypothesis $\neg P$ necessarily follows, such that
$\neg Q⟹\neg P.$

Examples

Let $n$ be a positive integer and let $d$ divide $n$. If $n$ is odd, then $d$ is odd.

We proceed by contraposition; it is easier to prove that if $d$ is even, then $n$ is even, since any even number is a multiple of $2$. We proceed by expressing $d$ as $d=2k$ for some $k\in \mathbb{Z}$. Because $d\mid n$, then $n=qd$ for some $q\in \mathbb{Z}$. When we substitute for $d$, $n=2(qk)$, which is definitely even since it is divisible by $2$. Since the contraposition holds, so does the original statement.

If $a^2$ is even, then $a$ is even.

We proceed by contraposition. Since $a$ is odd, it can be expressed as $2q+1$ for some quotient $q$. Then, $a^2$ can be expressed as $a^2=4q^2+4q+1=2(2q^2+2q)+1$. Since $2(2q^2+2q)$ is a multiple of $2$, it is clearly even. However, when we add $1$ to it it clearly becomes odd. Therefore, $a^2$ is also odd.

(Pigeonhole Principle) Let $n,k\in {\mathbb{Z}}^{+}$. Place $n$ objects into $k$ boxes. If $n>k$, then at least one box must contain multiple objects.

We proceed by contraposition. If all boxes contain exactly one object, then the number of objects is at most equal to the number of boxes, such that $n\le k$.