Proof by Contrapositive

Proof by contrapositive is a working tool across mathematics whenever a conclusion's negation is more tractable than its hypothesis. In elementary number theory it converts parity and divisibility claims (as in the worked $n^3 - 5n$ example) into direct computations. In real analysis, many "if convergent/continuous/differentiable then (property)" theorems are proved contrapositively, exactly as in the boundedness example, because definitions like convergence and continuity are naturally forward-usable while their negations ("unbounded," "discontinuous") are not. In topology, proofs that a space is not compact, not connected, or not Hausdorff routinely proceed by assuming the negation of the desired conclusion and deriving a violation of a hypothesis. In computer science and formal verification, contrapositive reasoning underlies the correctness proofs of many algorithms: to show "if the algorithm outputs 'reject' then the input is invalid," one often assumes the input is valid and shows the algorithm outputs 'accept.' In cryptography, security reductions frequently take the contrapositive form: "if an adversary can break the scheme (breaks $Q$'s negation), then the adversary can solve a presumed-hard problem (breaks $P$'s negation)" — precisely a contrapositive framing of "if the hard problem is infeasible, the scheme is secure." In statistics and hypothesis testing, the logic of rejecting a null hypothesis when data are "too extreme" mirrors contrapositive reasoning: assuming the null is true (a structured, forward-usable hypothesis) to derive a rare-event conclusion, whose failure supports rejecting the null. Finally, in circuit design and digital logic, De Morgan's laws combined with contraposition let engineers rewrite control conditions into equivalent, more efficient gate structures.

Ask the tutor: Can you show me how a proof by contrapositive turns into a proof by contradiction, step by step, using the same example?

Think of $P \Rightarrow Q$ as a promise: "whenever $P$'s territory is entered, $Q$'s territory is guaranteed." The promise is broken only in one way — being in $P$ but not in $Q$. Saying "if $\neg Q$ then $\neg P$" is just describing the same forbidden zone from the opposite corner: being outside $Q$ forces you outside $P$, which is exactly the statement that the forbidden combination (in $P$, outside $Q$) never occurs. Nothing about the promise has changed; we have only relabeled which corner of the picture we walk through first. Picture the universe of objects split into four regions by membership in $P$ and in $Q$. The implication $P\Rightarrow Q$ forbids exactly the region "$P$ true, $Q$ false." The contrapositive $\neg Q \Rightarrow \neg P$ forbids exactly the region "$Q$ false, $P$ true" — the identical region, described by entering through the $\neg Q$ door instead of the $P$ door. The inverse and converse, by contrast, forbid different regions, which is why they carry different, independent truth content.

An alternative, non-truth-table justification, useful for readers who prefer natural deduction: assume $P$ and suppose we have a proof of $\neg Q \Rightarrow \neg P$. To show $Q$, argue by cases on whether $Q$ or $\neg Q$ holds (law of excluded middle). If $Q$ holds we are done. If $\neg Q$ holds, then by the assumed $\neg Q \Rightarrow \neg P$ we get $\neg P$, contradicting the assumption $P$; from a contradiction, $Q$ follows by ex falso quodlibet. Either way $Q$ is derived, so $P \Rightarrow Q$. This derivation uses the law of excluded middle and ex falso, both valid in classical logic, confirming the equivalence without an explicit truth table.

Example 1 (Number theory: an asymmetric divisibility claim). Claim. Let $n$ be an integer. If $n^3 - 5n$ is odd, then $n$ is even. Here $P$ is "$n^3 - 5n$ is odd" and $Q$ is "$n$ is even." A direct attack assumes $n^3 - 5n$ odd and must somehow extract parity information about $n$ from a cubic expression — awkward. The contrapositive reverses this: assume $\neg Q$, namely $n$ is odd, and derive $\neg P$, namely $n^3 - 5n$ is even. Parity of $n$ propagates very cleanly through polynomial arithmetic, so this direction is easy. Proof by contrapositive. Suppose $n$ is odd, i.e. $n = 2k+1$ for some integer $k$. Compute

Actually, let's compute directly and transparently. With $n = 2k+1$:

So

Every term on the right is divisible by $4$, in particular by $2$:

Since $4k^3 + 6k^2 - 2k - 2$ is an integer, $n^3 - 5n$ is even. This is exactly $\neg P$: the negation of "$n^3-5n$ is odd." We have shown $\neg Q \Rightarrow \neg P$, namely "$n$ odd $\Rightarrow$ $n^3-5n$ even." By Contrapositive Equivalence, this proves $P \Rightarrow Q$: if $n^3 - 5n$ is odd, then $n$ is even. $\blacksquare$ Note the asymmetry deliberately built in: the original hypothesis $P$ involves a cubic expression, not a simple parity statement, which is precisely why arguing forward from $P$ is unattractive and arguing backward from $\neg Q$ is natural.

Example 2 (Real analysis: an $\varepsilon$–$N$ style claim). Claim. Let $(a_n)_{n \geq 1}$ be a sequence of real numbers, and suppose $(a_n)$ is bounded, meaning there exists $M > 0$ with $|a_n| \le M$ for all $n$. Let $L$ be a real number. If it is not the case that $a_n \to L$, one cannot in general conclude $(a_n)$ is unbounded — that's false and not our claim. Instead, consider a genuinely useful contrapositive-flavored claim: Claim (correct version). Let $(a_n)$ be a sequence of real numbers. If $(a_n)$ is unbounded, then $(a_n)$ does not converge to any real number $L$. Here $P$ is "$(a_n)$ is unbounded" and $Q$ is "$(a_n)$ does not converge to $L$" for an arbitrary fixed real $L$. Equivalently we prove the contrapositive: $\neg Q \Rightarrow \neg P$, i.e., "if $(a_n) \to L$ then $(a_n)$ is bounded." This is the natural direction because the definition of convergence hands us a concrete $N$ and $\varepsilon$ to work with, while "unbounded" as a hypothesis gives no starting point for producing a limit. Proof by contrapositive. Assume $\neg Q$: $a_n \to L$ for some real number $L$. By the definition of convergence, taking $\varepsilon = 1$, there exists $N \in \mathbb{N}$ such that for all $n \ge N$,

By the triangle inequality, for all $n \ge N$,

Now let

a well-defined real number since it is the maximum of a finite set of real numbers. For $n < N$ we have $|a_n| \le M$ by construction (it's one of the finitely many terms in the max), and for $n \geq N$ we showed $|a_n| < 1 + |L| \le M$. So $|a_n| \le M$ for every $n \ge 1$. This means $(a_n)$ is bounded, which is exactly $\neg P$. We have proven $\neg Q \Rightarrow \neg P$: convergence implies boundedness. By Contrapositive Equivalence, this proves $P \Rightarrow Q$: unboundedness implies non-convergence (to $L$, and since $L$ was an arbitrary real number, non-convergence to any real number). $\blacksquare$ This example illustrates the same asymmetry principle: "unbounded" is a purely negative, hard-to-use hypothesis (it says a universally quantified boundedness statement fails, without pointing to any particular structure), whereas "convergent" is richly structured (it hands you an $N$ for any $\varepsilon$), so proving the contrapositive is far more tractable than a direct assault on the original statement.