Prove P → Q by proving the equivalent ¬Q → ¬P
Proof by contrapositive is an elegant technique based on a fundamental fact of logic: the statement "if P then Q" is logically equivalent to "if not Q then not P." Instead of proving P → Q directly, we can prove ¬Q → ¬P, which is often easier! This isn't a roundabout method—it's proving the exact same thing in a different form.
Why P → Q and ¬Q → ¬P are the same statement in different forms
Understand when to use each technique and how they differ
Practice negating statements correctly to build the contrapositive
Work through proofs like "if n² is even, then n is even"
See why P → Q and ¬Q → ¬P are logically equivalent. They have the same truth values in every possible scenario!
| P | Q | P → Q | ¬Q | ¬P | ¬Q → ¬P | Match? |
|---|---|---|---|---|---|---|
| T | T | T | F | F | T | ✓ |
| T | F | F | T | F | F | ✓ |
| F | T | T | F | T | T | ✓ |
| F | F | T | T | T | T | ✓ |
Notice: P → Q and ¬Q → ¬P have identical truth values in every row!
P → Q ≡ ¬Q → ¬P. These are not just "related"—they're the exact same statement in different logical clothing. Proving one automatically proves the other. This is why contrapositive is so powerful: you're not taking a detour, you're walking the same path in reverse!
To prove an implication P → Q using the contrapositive:
The implication P → Q is only false when P is true and Q is false. The contrapositive ¬Q → ¬P is false in exactly the same situation. They have identical truth tables!
Use contrapositive when the negation of Q gives you something concrete to work with, or when proving P → Q directly seems awkward. It's especially useful for statements about divisibility, parity, and properties of numbers.
These two techniques are often confused! Let's clarify the differences and practice choosing the right approach.
| Aspect | Contrapositive | Contradiction |
|---|---|---|
| What you prove | An equivalent statement (¬Q → ¬P) | The original statement (P) by showing ¬P is impossible |
| What you assume | ¬Q (the negation of the conclusion) | ¬P (the negation of what you want to prove) |
| What you derive | ¬P (the negation of the hypothesis) | A logical impossibility (X ∧ ¬X) |
| Type of proof | Direct proof of an equivalent statement | Indirect proof via impossibility |
| Best used when | ¬Q gives useful concrete information | Direct/contrapositive seem hard, or proving existence/uniqueness |
Prove: "If n² is odd, then n is odd"
What's the best proof technique?
Walk through classic contrapositive proofs step by step. See how assuming ¬Q leads us to prove ¬P.
We want to prove: If n² is even, then n is even.
The converse of P → Q is Q → P (NOT equivalent!). The contrapositive is ¬Q → ¬P (equivalent). Don't mix them up—the converse is a completely different statement.
Be careful when negating statements. The negation of "n is even" is "n is odd" (not "n is negative"). The negation of "for all x" is "there exists x such that not..."
Sometimes a direct proof is simpler! Don't use contrapositive just because you can. Choose the approach that makes the proof clearest and most natural.