The Contrapositive Strategy

Change the Route Without Changing the Claim

In “The Direct Proof Strategy,” the proof began by assuming the hypotheses of an implication and deriving its conclusion. Sometimes that route is awkward: the conclusion may be easier to establish after changing what is assumed and what must be shown. The contrapositive makes that change without changing the logical content of the claim.

For an implication “if \(P\), then \(Q\),” its contrapositive is “if not \(Q\), then not \(P\).” These statements are logically equivalent. A contrapositive proof therefore establishes the original implication, but it starts from the failure of the conclusion and aims to rule out the hypothesis. This can be useful when the negation of the conclusion gives a concrete condition to work with.

The contrapositive is not the converse. The converse of “if \(P\), then \(Q\)” is “if \(Q\), then \(P\),” and it need not be true. Nor is a contrapositive proof the same as simply assuming the original hypothesis and conclusion are both false. The assumptions and target must be negated and exchanged in the correct way.

Proof. Suppose first that \(P\Rightarrow Q\) is true. To prove \(\neg Q\Rightarrow\neg P\), assume \(\neg Q\). If \(P\) were true, the implication \(P\Rightarrow Q\) would make \(Q\) true, contrary to \(\neg Q\). Thus \(P\) is false, so \(\neg P\) holds. This proves the contrapositive.

Conversely, suppose \(\neg Q\Rightarrow\neg P\) is true. Assume \(P\). We show that \(Q\) must hold. If \(Q\) were false, then \(\neg Q\) would hold, and the assumed contrapositive would give \(\neg P\), contradicting \(P\). Therefore \(Q\) holds, which proves \(P\Rightarrow Q\). The two implications are equivalent. \(\square\)

For a statement quantified over a domain, the same equivalence applies to each fixed object. A careful proof therefore begins by fixing an arbitrary object, then negating the conditional’s conclusion and hypothesis. For example, the negation of “for every \(x\in A\), if \(P(x)\), then \(Q(x)\)” is “there exists \(x\in A\) such that \(P(x)\) holds and \(Q(x)\) fails.” This is the Negating a Universal Implication result from “How to Recognize a Proof Strategy.”

Worked Examples: Finding a Useful Contrapositive

A common reason to use this strategy is that “not bounded” or “not Cauchy” can be expressed in terms of failure of a definition. In the next result, the contrapositive turns an assumption of unboundedness into a direct way to violate the Cauchy condition.

Proof. We prove the contrapositive: if \((a_n)\) is unbounded, then it is not Cauchy. Since the sequence is unbounded, every tail is unbounded. Indeed, if some tail \((a_n)_{n\geq N}\) were bounded, then the finitely many terms \(a_1,\ldots,a_{N-1}\) would also be bounded, and together these bounds would bound the entire sequence.

Fix any positive integer \(N\). The tail beginning at \(N\) is unbounded, so there is an index \(m\geq N\) such that \(|a_m|>|a_N|+1\). The triangle inequality implies

Consequently, for every \(N\), there are indices \(m,N\geq N\) whose terms are more than \(1\) apart. The Cauchy condition fails with tolerance \(1\): there is no stage after which every pair of terms is within \(1\) of one another. Thus an unbounded sequence is not Cauchy. By equivalence with its contrapositive, every Cauchy sequence is bounded. \(\square\)

A Sequential Test for Uniform Continuity

For functions, a contrapositive argument can expose a failure of uniform continuity as a pair of sequences. Uniform continuity requires one input distance to work throughout the domain. Its failure therefore gives pairs of inputs that become arbitrarily close while their function values remain separated by a fixed positive amount.

Proof. First suppose \(f\) is uniformly continuous. Let \((x_n)\) and \((y_n)\) be sequences in \(A\) such that \(|x_n-y_n|\to0\). Given \(\varepsilon>0\), uniform continuity supplies a \(\delta>0\) such that, for all \(x,y\in A\), if \(|x-y|<\delta\), then \(|f(x)-f(y)|<\varepsilon\). Since \(|x_n-y_n|\to0\), there is an \(N\) such that \(n\geq N\) implies \(|x_n-y_n|<\delta\). Hence \(n\geq N\) implies \(|f(x_n)-f(y_n)|<\varepsilon\), as required.

For the converse, we prove the contrapositive. Suppose \(f\) is not uniformly continuous on \(A\). Negating the definition of uniform continuity gives an \(\varepsilon_0>0\) such that for every \(\delta>0\), there are \(x,y\in A\) with \(|x-y|<\delta\) but \(|f(x)-f(y)|\geq\varepsilon_0\). For each positive integer \(n\), apply this statement with \(\delta=1/n\), and choose \(x_n,y_n\in A\) such that

The first inequality shows that \(|x_n-y_n|\to0\). The second shows that \(|f(x_n)-f(y_n)|\) does not tend to zero, since it is never less than the fixed positive number \(\varepsilon_0\). Thus failure of uniform continuity produces sequences that violate the stated sequence property. By the contrapositive, if the sequence property holds, \(f\) is uniformly continuous. \(\square\)

When the Contrapositive Helps—and What to Check

The strategy is most useful when the negation of the conclusion has a workable definition or gives a concrete witness. Unboundedness, failure of a limit, and failure of uniform continuity all provide such information. In the uniform-continuity theorem, the negated definition supplies an \(\varepsilon_0\) and pairs of points for every proposed \(\delta\); choosing \(\delta=1/n\) converts those witnesses into sequences.

A contrapositive proof still needs the same care as a direct proof. Check that each negation is correct, including the order of quantifiers. For instance, “for every \(\varepsilon>0\), there exists \(\delta>0\)” becomes “there exists \(\varepsilon_0>0\) such that for every \(\delta>0\)” when negated. Reversing that order would describe a different claim.

Also check the distinction between “less than” and “less than or equal to” when negating inequalities. The negation of \(|u|<\varepsilon\) is \(|u|\geq\varepsilon\), not \(|u|>\varepsilon\). Finally, once the contrapositive has been proved, say that it establishes the original implication. That final link makes the proof’s logical structure explicit.