A question says "prove that \sqrt{2} is irrational," or "show there are infinitely many primes," or "prove that no positive integer solutions exist for x^2 - 2y^2 = 0 with y > 0." Three different problems, one shared recipe. Every proof by contradiction runs the same three steps:
- Assume the negation of the conclusion. If the claim is P, assume \lnot P.
- Derive a contradiction. Chain lawful deductions until you reach something impossible — a statement and its negation both holding, a violated definition, a number that is both even and odd, a fraction that cannot be in lowest terms.
- Declare the original true. Since \lnot P led to an impossibility, \lnot P must be false. Therefore P is true.
That is the entire method. The technique lives in step 2 (deriving the contradiction), but steps 1 and 3 are the scaffolding you reach for the instant you recognise the right situation.
The recognition cue
The reflex fires on any of these stem patterns:
- "Prove that \sqrt{n} is irrational" for any non-square integer n.
- "Show that there is no largest prime."
- "Prove no rational solution exists for..."
- "Show that \log_2 3 is irrational."
- "Prove that a specific property P holds for some object" — and every direct argument you try gets stuck.
- "Disprove that..." — by exhibiting a contradiction when the claim is assumed true.
Each of these screams "direct proof is hard, contradiction is easy." The reason is simple: the negation \lnot P gives you a concrete, usable assumption ("suppose \sqrt{2} = p/q in lowest terms"), while a direct proof of P ("construct the irrationality") has nothing concrete to grab.
The logical spine
The equivalence that powers the method is this:
Double negation. To prove P, you equivalently disprove \lnot P. And to disprove \lnot P, you assume it and show it is logically impossible — i.e. leads to a contradiction. See Logic and Propositions for the truth-table justification.
Why this works as a proof: mathematics rests on consistency. If a set of assumptions entails a contradiction (a statement Q \land \lnot Q), one of those assumptions must be false. All your other assumptions are lawful theorems and definitions — they cannot be the false one. So the only suspect is the temporary assumption \lnot P. Therefore \lnot P is false, and P is true.
The walk-through — a concrete template
Claim. \sqrt{2} is irrational.
Step 1. Assume the negation: \sqrt{2} is rational. Then \sqrt{2} = p/q for integers p, q with no common factor (lowest terms), q \ne 0.
Step 2. Derive a contradiction.
- Square both sides: 2 = p^2/q^2, so p^2 = 2q^2.
- Therefore p^2 is even, so p is even (by the standard lemma). Write p = 2k.
- Substitute: (2k)^2 = 2q^2 \Rightarrow 4k^2 = 2q^2 \Rightarrow q^2 = 2k^2.
- Therefore q^2 is even, so q is even.
- But we assumed p and q have no common factor, and now both are even — both share the factor 2. Contradiction.
Step 3. Declare: the assumption "\sqrt{2} rational" is false. Hence \sqrt{2} is irrational. \blacksquare
The interactive three-stage reflex
The recognition patterns (where contradiction beats direct)
- Irrationality claims. Direct construction of an irrational number is hard. Contradiction gives you a rational p/q to squeeze.
- Non-existence claims. "There is no X with property Y" — assume there is, derive absurdity.
- Infinitude claims. "There are infinitely many primes" (Euclid's proof): assume finitely many, multiply them, add one, derive a new prime not in the list.
- Uniqueness claims. "Object X is the unique Y" — suppose two distinct X, X' both satisfy the property, derive X = X'.
- Extremal claims blocked by well-ordering. "No counterexample can be smallest" — if one existed, a smaller one would exist, contradiction.
If the stem fits any of these templates, reach for contradiction before trying direct.
What counts as a "contradiction"
The endpoint of step 2 must be unambiguously impossible. The standard landing-zones are:
- Explicit contradiction. A statement Q and its negation \lnot Q both appearing as derived facts.
- Violated definition. You assumed p/q in lowest terms, but derived \gcd(p, q) > 1.
- Violated theorem. You derived that an even integer equals an odd integer.
- Impossible arithmetic. You derived 1 = 0, or n < n, or x^2 < 0 for real x.
Anything that no mathematical world can contain is a legal landing. The contradiction does not need to be flashy — just impossible.
Two worked setups for the exam
Problem 1. Prove: if n^2 is even, then n is even.
This is the contrapositive by contradiction, not the direct. Assume the conclusion is false: n is odd. Then n = 2k+1 for some integer k. Square: n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1, which is odd. But we are given n^2 is even. Contradiction. Hence n is even. \blacksquare
Problem 2. Prove: there are infinitely many primes.
Assume finitely many primes: p_1, p_2, \ldots, p_n. Let N = p_1 p_2 \cdots p_n + 1. Then N is either prime itself or has a prime factor. Any prime factor of N leaves a remainder of 1 on division by each p_i, so cannot be any of the p_i. Therefore, there is a prime not in the list — contradicting "finitely many primes exhaust all of them." \blacksquare
The exam reflex
- See the stem triggers — irrational, no-such, infinitely many, unique, no-smallest.
- Write step 1 mechanically. "Suppose, for contradiction, that \lnot P..."
- Aim for a contradiction. The target is often: a number both even and odd, a fraction not in lowest terms, a new object outside a supposedly exhaustive list.
- Write step 3 mechanically. "This contradicts... therefore P is true."
Steps 1 and 3 are boilerplate. All your energy goes into step 2, and the trigger is pattern recognition on the stem.
Related: Logic and Propositions · Proof by Contradiction · Negation of If A Then B Is A and Not B · Proof by Contrapositive