Mathematics.

proof theory

Proof by Contrapositive

Mathematical Logic15 minDifficulty2 out of 10

You should know: proof techniques

Overview

Proof by contrapositive establishes a conditional statement P → Q by instead proving the logically equivalent statement ¬Q → ¬P: assume the conclusion fails and show the hypothesis must fail too. This works because p → q and ¬q → ¬p are logically equivalent (identical truth tables), so proving one legitimately proves the other. Unlike proof by contradiction, which assumes ¬P and can invoke any accumulated fact to reach an arbitrary contradiction, contrapositive proof is a direct proof of a specific different statement (¬Q → ¬P) and is accepted even in constructive/intuitionistic logic. It is especially useful when the direct implication P → Q is hard to unpack but its negated, reversed form is comparatively straightforward — often when Q's negation gives a clean algebraic or structural property to work with.

Intuition

If 'being a square implies being a rectangle' is true, then logically 'not being a rectangle implies not being a square' must also be true — these are just two ways of stating the exact same fact, seen from opposite directions. Proof by contrapositive exploits this by picking whichever direction is algebraically easier: often 'if n² is odd then n is odd' is awkward to attack head-on, but its contrapositive 'if n is even then n² is even' is immediate, since you can just write n=2k and square it — so instead of wrestling with oddness directly, you prove the cleaner evenness statement and get the original for free.

Formal Definition

Definition

The logical basis for proof by contrapositive is the tautology:

(P→Q)≡(¬Q→¬P)(P \rightarrow Q) \equiv (\neg Q \rightarrow \neg P)
Contrapositive equivalence
To prove P→Q, instead assume ¬Q and derive ¬P.\text{To prove } P \rightarrow Q, \text{ instead assume } \neg Q \text{ and derive } \neg P.
Proof strategy

Worked Examples

  1. State the contrapositive: if n is even, then n² is even.

    ¬Q→¬P: n even  ⟹  n2 even\neg Q \rightarrow \neg P: \ n \text{ even} \implies n^2 \text{ even}

  2. Assume n is even, so n = 2k for some integer k.

    n=2kn = 2k

  3. Then n² = 4k² = 2(2k²), which is even, proving the contrapositive and hence the original statement.

    n2=2(2k2) is evenn^2 = 2(2k^2) \text{ is even}

Answer: The contrapositive holds, so by logical equivalence, n² odd implies n odd.

Practice Problems

Difficulty 2/10

Prove by contrapositive: if 5n+3 is even, then n is odd.

Difficulty 3/10

Prove by contrapositive: for integers a, b, if ab is odd, then a is odd and b is odd.

Difficulty 3/10

Prove by contrapositive: if x² − 6x + 5 ≠ 0, then x ≠ 1 and x ≠ 5.

Quiz

The contrapositive of P → Q is:
Proof by contrapositive is preferred over proof by contradiction when:
Unlike full proof by contradiction, proof by contrapositive:

Summary

  • Proof by contrapositive proves P → Q by directly proving the logically equivalent ¬Q → ¬P.
  • It relies only on the tautology (P→Q) ≡ (¬Q→¬P), not on the law of excluded middle, so it's accepted in constructive logic.
  • It shines when negating the conclusion yields a concrete, easy-to-manipulate hypothesis, as in classic even/odd divisibility proofs.

References

  1. WebsiteWikipedia — Contraposition