1
Contraposition proves an equivalent statement
p → q ≡ ¬q → ¬p (“The Conditional and Its Relatives”), so proving one proves the other. Nothing is assumed beyond the new hypothesis ¬q.
Lesson · Logic and Proof · Proof
Contraposition and Contradiction
To prove p → q by contraposition, prove ¬q → ¬p instead — a different theorem with the same meaning. To prove s by contradiction, assume ¬s and derive an impossibility. They are not the same technique.
contraposition prove ¬q → ¬p an EQUIVALENT statement
contradiction assume ¬s, derive F any absurdity will do
Use contraposition when ¬q is easier to work with than p.
Use contradiction when ¬s gives you something concrete to hold.
Two indirect routes
Core ideas
What this lesson establishes
Both techniques replace a hard target with an easier one. They differ in what they assume and what they must produce.
2
Contradiction assumes the negation of the goal
You assume ¬s and derive something false. The falsehood may be anything: 0 = 1, a number both even and odd, a contradiction of a hypothesis.
3
They are often confused, and the difference matters
A "proof by contradiction" that assumes p ∧ ¬q and derives ¬p is really contraposition with extra steps. Naming it correctly makes it shorter.
The material
Indirect proof
Each technique, a worked instance, and the rule for choosing between them.
Proof by contraposition
Definition · Proof by contraposition
To prove p → q, prove ¬q → ¬p. Since the two are logically equivalent, a proof of either is a proof of both.
Theorem · If n² is even then n is even
For every integer n, if n² is even then n is even.
We prove the contrapositive: if n is odd then n² is odd.
Let n be an odd integer, so n = 2k + 1 for some integer k. Then n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd since 2k² + 2k is an integer.
The contrapositive holds, so the original statement holds.
□
Compare with the direct attempt. Assuming n² is even gives n² = 2m, and there is nowhere useful to go: extracting information about n from a statement about n² requires the unique factorisation of Number Theory and Cryptography. The contrapositive hands you n itself, in a form you can compute with. That asymmetry is the whole reason to choose it.
Proof by contradiction
Definition · Proof by contradiction
To prove s, assume ¬s and derive a statement known to be false. Since a false conclusion cannot follow from a true assumption, ¬s must be false, so s holds.
Theorem · √2 is irrational
There is no rational number whose square is 2.
Suppose, for contradiction, that √2 is rational. Then √2 = a/b for integers a, b with b ≠ 0, and we may take the fraction in lowest terms, so a and b share no common factor greater than 1.
Squaring: 2 = a²/b², hence a² = 2b². So a² is even, and by the theorem above a is even. Write a = 2c.
Substituting: 4c² = 2b², so b² = 2c². Then b² is even, so b is even. But then a and b are both divisible by 2, contradicting that the fraction was in lowest terms.
The assumption is therefore false, and √2 is irrational.
□
That proof is worth studying for its structure as much as its result. The contradiction is not with a law of arithmetic but with a condition we imposed ourselves — lowest terms — and imposing it was the move that made the proof possible.
Choosing between them
- The statement is a conditional and ¬q is concrete: use contraposition. "n is odd" is workable; "n² is even" is not.
- The statement asserts non-existence or impossibility: use contradiction. Assuming the thing exists gives you an object to work with, which is the only handle available.
- The statement is a conditional and you find yourself assuming p ∧ ¬q and deriving ¬p: you are doing contraposition. Say so — the proof gets shorter and clearer.
Theorem · There are infinitely many primes (Euclid)
For any finite list of primes, there is a prime not on it.
Suppose p₁, …, pₙ are primes and consider N = p₁p₂⋯pₙ + 1. N is greater than 1, so it has a prime factor q.
If q were one of the pᵢ, it would divide both the product p₁⋯pₙ and N, hence their difference, which is 1. No prime divides 1, so q is not on the list.
Every finite list of primes therefore omits one, so no finite list contains them all.
□
This is often presented as a proof by contradiction — "assume finitely many primes" — but as written it is direct and constructive: given any list, it produces a prime not on it. That is a stronger result, and it is worth noticing that the contradiction was never needed.
Interactive
Truth table
Every assignment, evaluated
Method
Choosing and executing an indirect proof
Try direct first. Indirect methods are answers to a specific difficulty.
1
Attempt the direct proof and notice where it stalls
The stall is diagnostic. Unable to use p? Try contraposition. Nothing to grab hold of at all? Try contradiction.
2
For contraposition, write both negations first
State ¬q → ¬p explicitly before proving anything. Negating the wrong part produces the inverse, which is not equivalent.
3
For contradiction, say what you are assuming
"Suppose, for contradiction, that…" — and keep that assumption visibly separate from what you have proved.
4
Name the contradiction when you reach it
"This contradicts the assumption that the fraction was in lowest terms." A reader must not have to search for what went wrong.
Indirect proof
Score 0 / 0Choose the answer you can justify.
If 3n + 2 is odd then n is odd
Direct is awkward; the contrapositive is two lines.
Contrapositive: if n is EVEN then 3n + 2 is EVEN.
Let n be even, so n = 2k for some integer k.
3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1)
3k + 1 is an integer, so 3n + 2 is even.
The contrapositive holds, hence so does the original. ∎
The direct route would start from "3n + 2 is odd", giving 3n + 2 = 2m + 1 and so 3n = 2m − 1 — and then needs an argument about why 3n odd forces n odd. Not impossible, but longer, and the contrapositive avoided it by handing us n directly.
Common mistakes
1
Proving the inverse instead of the contrapositive¬p → ¬q is the inverse and is not equivalent to p → q. The contrapositive negates AND swaps.
2
Calling every indirect proof a contradictionIf the falsehood you derive is ¬p and p was the hypothesis, you have proved the contrapositive. Naming it correctly removes an unnecessary assumption from the proof.
3
Not saying which assumption the contradiction contradictsA proof that ends "contradiction" without saying with what leaves the reader to reconstruct the argument. Name it.
Check your understanding
✓
Finish when you can pick the technique from the shape of the claim.
Prove "if n is an integer and n² + 5 is odd then n is even" — and be able to say, before starting, which technique you will use and why the other would be harder.
Note: Constructive mathematics rejects proof by contradiction for existence claims: knowing that no counterexample exists is not the same as being able to produce an example. That distinction has no consequences on this path, but Euclid's proof above is worth revisiting with it in mind.