Proof Techniques
Mathematical proof is the mechanism by which conjectures become theorems. A proof is a finite sequence of logical steps, each justified by axioms, definitions, or previously established results, that establishes the truth of a mathematical statement beyond doubt. This skill catalogs 13 proof techniques with canonical worked examples, strategy selection heuristics, and readability guidance.
Agent affinity: euclid (geometric and structural proofs), polya (strategy selection)
Concept IDs: math-equations-expressions, math-systems-polynomials, math-pattern-recognition
The Proof Toolbox at a Glance
| # | Technique | Best for | Key signal | |---|---|---|---| | 1 | Direct proof | Default for implications | Can build Q from P step by step | | 2 | Contrapositive | P is hard to use directly | neg-Q gives a more concrete hypothesis | | 3 | Contradiction | Non-existence, irrationality, infinity | Negation yields a concrete object that self-destructs | | 4 | Cases | Natural partition of hypotheses | Parity, sign, size, set membership | | 5 | WLOG | Symmetric variables | Cases would repeat the same argument | | 6 | Vacuous/Trivial | Empty-set or always-true conclusions | Antecedent is false or consequent is always true | | 7 | Biconditional | "If and only if" statements | Must prove both directions | | 8 | Counterexample | Disproving universal claims | One witness to failure suffices | | 9 | Existence | "There exists" statements | Constructive (exhibit) or non-constructive (probabilistic/LEM) | | 10 | Uniqueness | "There exists exactly one" | Assume two, show equal | | 11 | Induction | Claims over N or recursive structures | Weak, strong, or structural depending on domain | | 12 | Pigeonhole / Double counting | Combinatorial existence, identities | More objects than containers; count the same set two ways | | 13 | Diagonal / Invariants | Uncountability, impossibility | Construct a witness that differs from every listed element; find a preserved quantity |
Technique 1 — Direct Proof
Pattern: To prove P implies Q, assume P and derive Q.
Logical basis: Implication introduction. This is the default technique and should be attempted first for any implication.
Worked example. If n is an even integer, then n-squared is even.
Proof. Let n be an even integer. Then n = 2k for some integer k. We compute n^2 = (2k)^2 = 4k^2 = 2(2k^2). Since 2k^2 is an integer, n^2 = 2m where m = 2k^2, so n^2 is even.
When to use. Always try direct proof first. Most theorems in undergraduate courses yield to direct proof. Only switch techniques when the direct path stalls — typically when the hypothesis P does not provide enough structure to build toward Q.
When it stalls. You cannot find a way to use P to construct Q. This often signals that the natural reasoning direction is from neg-Q to neg-P (contrapositive), or that assuming neg-Q produces an immediate contradiction.
Technique 2 — Proof by Contrapositive
Pattern: To prove P implies Q, prove the logically equivalent statement: neg-Q implies neg-P.
Logical basis: Contraposition equivalence. P => Q is equivalent to (not Q) => (not P). The proof mechanism after forming the contrapositive is direct proof.
Worked example. If n^2 is even, then n is even.
Why direct proof stalls: Assuming n^2 = 2k, we need to extract n = 2m, but taking square roots of integers is not a direct algebraic operation.
Contrapositive: If n is odd, then n^2 is odd.
Proof. Suppose n is odd. Then n = 2k + 1 for some integer k. We compute n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1. Since 2k^2 + 2k is an integer, n^2 is odd. The contrapositive holds, so the original implication holds.
When to use. When neg-Q gives a more concrete, manipulable hypothesis than P. In this example, "n is odd" lets you write n = 2k + 1 and compute directly; "n^2 is even" leaves you fighting the square root.
Technique 3 — Proof by Contradiction (Reductio ad Absurdum)
Pattern: To prove P, assume neg-P and derive a contradiction.
Logical basis: (neg-P => contradiction) implies P. This is classically valid. In intuitionistic logic, it gives only neg-neg-P; the jump to P requires the law of excluded middle.
Worked example. The square root of 2 is irrational.
Proof. Suppose for contradiction that sqrt(2) is rational. Then sqrt(2) = p/q where p, q are integers, q is nonzero, and gcd(p, q) = 1. Squaring: 2 = p^2/q^2, so p^2 = 2q^2. Thus p^2 is even, so p is even (by Technique 2). Write p = 2r. Then 4r^2 = 2q^2, so q^2 = 2r^2, meaning q is even. But then both p and q are even, contradicting gcd(p, q) = 1. Therefore sqrt(2) is irrational.
When to use. When the negation of the conclusion gives you a concrete object to reason about, and that object collides with known facts. Especially useful for:
- Non-existence claims: "There is no x such that P(x)" — assume such x exists, derive contradiction.
- Infinity arguments: "There are infinitely many primes" — assume finitely many, construct a new one (Euclid).
- Irrationality: Assume rational form, derive coprimality contradiction (as above).
When NOT to use. Do not reach for contradiction when a direct proof or contrapositive works cleanly. Unnecessary contradiction proofs obscure the logical structure and make verification harder.
Technique 4 — Proof by Cases
Pattern: To prove P, partition the hypothesis space into cases C_1, C_2, ..., C_n that exhaust all possibilities, and prove P separately in each case.
Logical basis: Disjunction elimination.
Worked example. For any integer n, n^2 + n is even.
Proof. Let n be an integer. We consider two cases.
Case 1: n is even. Then n = 2k. So n^2 + n = 4k^2 + 2k = 2(2k^2 + k), which is even.
Case 2: n is odd. Then n = 2k + 1. So n^2 + n = (2k+1)^2 + (2k+1) = 4k^2 + 4k + 1 + 2k + 1 = 4k^2 + 6k + 2 = 2(2k^2 + 3k + 1), which is even.
In both cases, n^2 + n is even.
When to use. When the hypothesis or object has a natural partition: parity (even/odd), sign (positive/zero/negative), size comparisons, set membership (x in S vs x not in S).
Common mistake. Forgetting to cover a case. Splitting into "x > 0" and "x < 0" without addressing x = 0 invalidates the proof.
Technique 5 — Without Loss of Generality (WLOG)
Pattern: When multiple symmetric cases would require identical arguments, argue one case and assert the others follow by symmetry.
Worked example. For any real numbers x and y, |x - y| >= ||x| - |y||.
Proof. Without loss of generality, assume |x| >= |y|. (If |y| > |x|, swap x and y; the inequality is symmetric.) Then ||x| - |y|| = |x| - |y|. By the triangle inequality: |x| = |(x - y) + y| <= |x - y| + |y|. So |x| - |y| <= |x - y|, which is the desired result.
Critical discipline. WLOG is only valid when cases are genuinely interchangeable. Asserting "WLOG x > 0" when the argument for x < 0 would differ is a logical error. Whenever you write WLOG, verify that the full proof reconstructs by substitution alone.
Technique 6 — Vacuous and Trivial Proofs
Vacuous proof pattern: To prove P => Q, show that P is false. The implication holds vacuously because an implication with a false antecedent is true.
Example. For every x in the empty set, x is positive. There are no elements, so the statement holds vacuously.
Trivial proof pattern: To prove P => Q, show that Q is true regardless of P.
Example. For every real number x, if x >= 0, then x^2 + 1 > 0. Since x^2 >= 0 for all real x, we have x^2 + 1 >= 1 > 0 independently of the hypothesis. The implication holds trivially.
When to use. Rarely as primary techniques. More commonly they appear as observations within larger proofs — "this case is vacuous because the set is empty" or "the inequality holds trivially since both sides are positive."
Technique 7 — Biconditional Proof
Pattern: To prove P if and only i