Proof by Contrapositive

When the forward implication feels sticky, turn it around: prove that failing the conclusion would have forced the hypothesis to fail too.

The idea

Proof by contrapositive proves an implication $P \Rightarrow Q$ by proving $\neg Q \Rightarrow \neg P$ instead. The two statements are logically equivalent — each is false in exactly one situation, namely when $P$ holds and $Q$ fails — so a proof of either is a proof of both.

The switch pays when the negated conclusion is easier to reason from than the hypothesis. Consider the claim that if $x + y \geq 2$, then at least one of $x$ and $y$ is at least $1$. A direct proof assumes $x + y \geq 2$, which says nothing about $x$ or $y$ separately. The contrapositive assumes instead that both $x < 1$ and $y < 1$, and adding the two inequalities gives $x + y < 2$ — the negated hypothesis — completing the proof.

Keep the contrapositive distinct from two similar statements. Reversing the implication without negating gives the converse $Q \Rightarrow P$, and negating without reversing gives the inverse $\neg P \Rightarrow \neg Q$. The converse and inverse are contrapositives of each other, so they are equivalent to each other — but neither is equivalent to the original, and proving either one proves nothing about it.

Ways to work on it

• Walkthrough. Learn the logic of contrapositives through parity examples.
• Practice. Distinguish a true contrapositive from a tempting but wrong converse.
• Hardest. Use a contrapositive argument to prove a function is injective.

Not sure where to start? Take the ten-question placement test.