Helpful context:

Proof is the mechanism by which mathematics achieves certainty. An argument in ordinary discourse persuades; a proof compels. The distinction matters because mathematics is not empirical - no finite collection of examples establishes a universal claim, and no appeal to intuition substitutes for logical necessity. A proof is a finite sequence of steps, each following from the previous by rules of inference, that forces the conclusion regardless of the reader’s prior beliefs.

But proofs are not all the same. They come in different flavors, and choosing the right technique for a given problem is a skill developed through exposure to many examples. Some statements have hypotheses rich enough to march straight to the conclusion. Others are easier approached from the negation. Statements about natural numbers often yield to induction. Statements about processes and games often yield to invariants. And some existence claims are most cleanly handled by showing the object must exist, without ever constructing it.

What follows is a catalog of the main techniques, with worked examples. The goal is not just to know the names, but to develop the judgment to recognize which technique a given problem calls for.

Direct Proof

The simplest structure: assume the hypothesis, apply definitions and previously established facts, arrive at the conclusion without detour.

Structure. To prove $P \Rightarrow Q$: assume $P$, then derive $Q$ by a chain of equalities, inequalities, or logical implications.

Example. Prove: if $n$ is odd, then $n^2$ is odd.

Proof. Assume $n$ is odd. By definition, $n = 2k + 1$ for some integer $k$. Then

$$n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1.$$

Since $2k^2 + 2k$ is an integer, $n^2$ has the form $2m + 1$ and is therefore odd. $\square$

The hypothesis gave us a concrete representation to compute with. That is the hallmark of a situation where direct proof works: the hypothesis hands you a handle - a formula, a structural property, a bound - that you can carry forward algebraically or logically until the conclusion appears.

When it works. The hypothesis is strong or explicit enough that manipulating it directly reaches the goal. If you find yourself stuck after assuming $P$ with no path forward, consider contrapositive or contradiction.

Proof by Contradiction (Reductio ad Absurdum)

Assume the negation of what you want to prove, then derive a statement that is false. Since a chain of valid reasoning from a true premise cannot produce a false conclusion, the assumed negation must be false - so the original statement is true.

Structure. To prove $P$: assume $\neg P$, derive a contradiction ($\bot$).

Example 1. Prove: $\sqrt{2}$ is irrational.

Proof. Assume for contradiction that $\sqrt{2}$ is rational. Then $\sqrt{2} = \frac{p}{q}$ for integers $p, q$ with $q \neq 0$ and $\gcd(p,q) = 1$ (the fraction is in lowest terms). Squaring both sides gives $2 = \frac{p^2}{q^2}$, so $p^2 = 2q^2$. This means $p^2$ is even, which (by direct proof, or the earlier example via contrapositive) implies $p$ is even. Write $p = 2m$. Then $4m^2 = 2q^2$, so $q^2 = 2m^2$, which means $q^2$ is even and hence $q$ is even. But then $2 \mid p$ and $2 \mid q$, contradicting $\gcd(p,q) = 1$. $\square$

Example 2. Prove: there are infinitely many primes.

Proof (Euclid). Assume for contradiction that there are finitely many primes, say $p_1, p_2, \ldots, p_k$. Consider $N = p_1 p_2 \cdots p_k + 1$. Since $N > 1$, it has at least one prime divisor $p$. But $p$ cannot be any of $p_1, \ldots, p_k$, because $N \equiv 1 \pmod{p_i}$ for each $i$, so no $p_i$ divides $N$. This contradicts the assumption that $p_1, \ldots, p_k$ are all the primes. $\square$

When it works. The negation $\neg P$ is concrete and useful - it gives you an assumption with real teeth. Irrationality becomes a fractional representation; finitude becomes an explicit list. These are things you can compute with. When $P$ itself is abstract and hard to work forward from, assuming $\neg P$ often gives you more to grab.

Proof by Contrapositive

The contrapositive of $P \Rightarrow Q$ is $\neg Q \Rightarrow \neg P$. These are logically equivalent - each is true if and only if the other is - so proving the contrapositive is a complete proof of the original implication.

Structure. To prove $P \Rightarrow Q$: assume $\neg Q$, derive $\neg P$ directly.

Example. Prove: if $n^2$ is even, then $n$ is even.

Direct approach: $n^2$ even means $n^2 = 2k$, but it is not immediately clear how to extract the parity of $n$ from this. Contrapositive: assume $n$ is odd (i.e., $\neg Q$: $n$ is not even), and derive $n^2$ is odd (i.e., $\neg P$: $n^2$ is not even). We already proved this in the direct proof section. Done. $\square$

Contrapositive vs. contradiction. These are related but distinct. In a contrapositive proof, you assume $\neg Q$ and work directly toward $\neg P$ - no contradiction is needed, and you never assume $\neg P$. In a contradiction proof, you assume $\neg(P \Rightarrow Q)$, which means assuming both $P$ and $\neg Q$ simultaneously, and look for any contradiction. Contrapositive proofs are cleaner when the structure is simply “the other direction is easier.” Contradiction is more powerful but introduces an additional assumed premise that can obscure what is doing the work.

When it works. $\neg Q$ gives you a stronger or more explicit condition than $P$. Knowing something is not in a set, not prime, not continuous is sometimes the more useful assumption.

Mathematical Induction

For statements of the form $\forall n \in \mathbb{N}, P(n)$, induction decomposes the proof into two finite obligations that together imply the infinite conclusion.

Structure.

  • Base case: prove $P(0)$ (or $P(1)$, or whatever the first case is).
  • Inductive step: prove $P(k) \Rightarrow P(k+1)$ for arbitrary $k$.

The two together establish $P(n)$ for all $n$ by a chain that can be unwound step by step from the base.

Example. Prove: $\displaystyle\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$.

Base case ($n = 1$): $\sum_{i=1}^1 i = 1 = \frac{1 \cdot 2}{2}$. ✓

Inductive step: Assume $\sum_{i=1}^k i = \frac{k(k+1)}{2}$. Then

$$\sum_{i=1}^{k+1} i = \left(\sum_{i=1}^k i\right) + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}.$$

This is exactly the formula with $n = k+1$. $\square$

Strong Induction

In strong induction, the inductive step assumes $P(j)$ for all $j < k$, not just $j = k-1$. The conclusion is the same; the hypothesis is stronger. Strong induction is needed when a case depends on multiple earlier cases, not just the immediately preceding one.

Example. Prove: every integer $n \geq 2$ has a prime factorization.

Base case ($n = 2$): $2$ is prime, and $2$ itself is a prime factorization.

Inductive step: Let $n > 2$ and assume every integer $m$ with $2 \leq m < n$ has a prime factorization. If $n$ is prime, then $n$ is its own factorization. If $n$ is composite, then $n = ab$ with $2 \leq a, b < n$. By the inductive hypothesis, $a$ and $b$ each have prime factorizations; concatenating them gives a prime factorization of $n$. $\square$

The key: $n = ab$ might have $a$ far from $n-1$, so we need the hypothesis for all smaller values, not just the predecessor.

Well-Ordering Principle

An equivalent formulation: every nonempty subset of $\mathbb{N}$ has a least element. This is logically equivalent to induction over $\mathbb{N}$. Proofs using well-ordering often proceed by contradiction: assume the set of counterexamples is nonempty, take its least element $n$, and derive a contradiction by constructing a smaller counterexample - contradicting minimality. The style differs but the logical content is the same.

When it works. Any statement indexed by $\mathbb{N}$, or any recursive structure (trees, lists, strings). If a problem has a “one step further” structure - where each instance reduces to smaller instances - induction is almost always the right tool.

Invariants

An invariant is a quantity or predicate that is preserved by every step of a process. If you can identify what remains constant, you can draw conclusions about all states of the system, including those reachable only after many steps.

Structure. Identify a quantity $I$ such that:

  1. $I$ holds at the start.
  2. If $I$ holds before any step, it holds after.
  3. The invariant at the end implies your desired conclusion.

Example 1: the mutilated chessboard. Take an $8 \times 8$ chessboard and remove two diagonally opposite corners (both the same color, say both white). Can you tile the remaining 62 squares with 31 dominoes?

No - and the invariant shows why. Color the board in the standard checkerboard pattern. Each domino, wherever it is placed, covers exactly one black square and one white square. So after placing any number of dominoes, the number of covered black squares equals the number of covered white squares. But the standard $8 \times 8$ board has 32 black and 32 white squares, and removing two white corners leaves 32 black squares and 30 white squares. A complete tiling would require equal coverage, so no tiling exists. $\square$

The invariant here is the parity of the coloring. Notice that no calculation about domino positions was needed - just the existence of the invariant.

Example 2: DFA state invariants. In the automata-theory context, the correctness of a DFA is established by a state invariant. Assign to each state $q_i$ a predicate $P_i$ describing what it means to arrive in $q_i$ after reading some prefix of the input. The invariant: after reading any prefix $w$, if the DFA is in state $q_i$, then $P_i(w)$ holds. Verify it holds at the start (on $\varepsilon$, in the start state), and that every transition preserves it. Then the accepting states' predicates imply membership in the language, giving correctness. This is precisely the pattern from loop invariants in program verification - the DFA is a program, states are control locations, and the invariant certifies partial correctness.

Monovariants and Termination

A monovariant is a quantity that strictly increases (or strictly decreases) with every step and is bounded. Its existence guarantees termination: the process cannot run forever. If every step strictly decreases a non-negative integer, the process halts. If a real-valued quantity decreases by at least $\epsilon > 0$ per step and is bounded below, same conclusion. Monovariants are the standard tool for proving termination of algorithms and games: define the measure, show it decreases, note it is bounded.

When it works. Iterative processes, combinatorial games, sequences of operations where you need to reason about all reachable configurations without enumerating them. If the process has too many steps to trace case by case, look for an invariant.

Existence Proofs

To prove $\exists x, P(x)$, you have two strategies: find the object explicitly, or show it must exist without finding it.

Constructive Proofs

Exhibit the object. The proof works by construction - you write down the witness and verify it satisfies $P$. Constructive proofs are algorithmically meaningful: the construction is often an algorithm for finding the object.

Example. Prove there exists a prime greater than 1000. Construction: run a primality test on 1009; it is prime. $\square$

(More interesting examples: Euclid’s proof that there are infinitely many primes constructs an explicit integer $N = p_1 \cdots p_k + 1$ that must have a new prime factor - this is a constructive argument inside a proof by contradiction.)

Non-Constructive Proofs

Prove existence without exhibiting the object. The most elegant instance is the probabilistic method: define a probability space over some set of objects, compute the expected value of a relevant quantity, and conclude that the object achieving that value (or better) must exist.

Example (Ramsey-type bound). Show that there exists a 2-coloring of the edges of $K_n$ (the complete graph on $n$ vertices) with no monochromatic clique of size $k$, provided $\binom{n}{k} 2^{1-\binom{k}{2}} < 1$. A clique of size $k$ is a set of $k$ vertices that are all mutually connected - every pair has an edge between them. A monochromatic clique is one where all those edges share the same color.

Color each edge independently red or blue with probability $\frac{1}{2}$. For a fixed set $S$ of $k$ vertices, the probability that all $\binom{k}{2}$ edges among them are the same color is $2 \cdot 2^{-\binom{k}{2}} = 2^{1-\binom{k}{2}}$. By a union bound over all $\binom{n}{k}$ choices of $S$, the probability that some $k$-clique is monochromatic is at most $\binom{n}{k} 2^{1-\binom{k}{2}}$. If this is less than 1, the complementary event - no monochromatic $k$-clique - has positive probability, so such a coloring exists. $\square$

No specific coloring was produced. The argument only shows the probability of failure is less than 1.

Constructive vs. non-constructive. Constructive proofs are preferred when you need an algorithm or a specific example. Non-constructive proofs often give better bounds and require less case analysis, but they can leave you with existence and no procedure for finding the object. In combinatorics and theoretical computer science, both are indispensable.

Diagonalization

Cantor’s diagonalization argument is one of the most elegant proof techniques in mathematics. The idea: construct an object that differs from every element of a given list, thereby showing the list is incomplete.

Theorem (Cantor). The real numbers are uncountable - there is no surjection from $\mathbb{N}$ to $\mathbb{R}$.

Proof. Suppose for contradiction that $\mathbb{R}$ is countable, so there is a list $r_1, r_2, r_3, \ldots$ containing every real number. Write each $r_i$ in decimal:

$$r_i = \langle\text{integer part}\rangle.\ d_{i,1}\ d_{i,2}\ d_{i,3}\ \cdots$$

where $d_{i,j}$ is the $j$-th decimal digit of $r_i$. Construct a real number $x$ by setting its $j$-th decimal digit to

$$d_j = \begin{cases} 5 & \text{if } d_{j,j} \neq 5 \\ 6 & \text{if } d_{j,j} = 5 \end{cases}$$

Then $x$ differs from $r_1$ in the first decimal place, from $r_2$ in the second, from $r_j$ in the $j$-th - so $x \neq r_j$ for every $j$. Thus $x$ is not in the list, contradicting the assumption that the list contains every real. $\square$

(The specific choice of digits 5 and 6 sidesteps ambiguities from representations like $0.999\ldots = 1.000\ldots$.)

The diagonal argument carries over directly to theoretical computer science.

Theorem. The halting problem is undecidable: there is no program that, given any program $M$ and input $w$, correctly determines whether $M$ halts on $w$.

Proof. A program is just a finite string of characters - its source code, or equivalently its compiled binary. Strings can be passed as inputs to programs; your shell does this every time you run a command with arguments. This means a program can receive another program’s source code as input and inspect or simulate it. It also means a program can be given its own source code as input - there is nothing circular about this, since the source code is just text that happens to describe the program reading it.

Suppose for contradiction that a halting decider $H$ exists, where $H(M, w)$ outputs YES if $M$ halts on $w$ and NO otherwise. To see the diagonal structure, imagine listing all programs $P_1, P_2, P_3, \ldots$ (this is possible since programs are finite strings, and finite strings over a finite alphabet are countable) and arranging them in an infinite table: row $i$ is program $P_i$, column $j$ is input $P_j$, and the entry $(i, j)$ records whether $P_i$ halts on input $P_j$.

Now construct a program $D$ that, on input $P_i$:

  1. Runs $H(P_i, P_i)$ - asking whether $P_i$ halts when given itself as input (the diagonal entry $(i,i)$).
  2. If $H$ says YES (i.e., $P_i$ halts on $P_i$), then $D$ loops forever.
  3. If $H$ says NO (i.e., $P_i$ does not halt on $P_i$), then $D$ halts immediately.

$D$ is itself a program, so it appears somewhere in the list - say $D = P_k$. Ask what happens when $D$ runs on input $P_k$ (the diagonal entry $(k, k)$):

  • If $D$ halts on $P_k$: then step 2 says $D$ must loop. Contradiction.
  • If $D$ loops on $P_k$: then step 3 says $D$ must halt. Contradiction.

Either way, $H$ cannot exist. $\square$

This is exactly Cantor’s diagonal: the table of halt/loop decisions plays the role of the table of decimal digits, and $D$ is constructed to differ from program $P_i$ on the diagonal entry $(i,i)$, just as Cantor’s $x$ differed from $r_i$ in the $i$-th decimal place.

When it works. Showing that one infinity is strictly larger than another, or that no enumeration can capture all objects of a given type. The technique requires that you can construct an object by independently specifying its “coordinate” in each dimension - one entry per row of the supposed enumeration.

Summary

Technique Core move Best when
Direct Hypothesis $\to$ conclusion Hypothesis gives a strong handle
Contradiction Assume $\neg P$, derive $\bot$ Negation is easier to manipulate
Contrapositive Prove $\neg Q \Rightarrow \neg P$ $\neg Q$ is stronger than $P$
Induction Base case + inductive step Indexed by $\mathbb{N}$, recursive structure
Invariant Preserved quantity across all steps Iterative process, combinatorial game
Constructive existence Exhibit the object Need an algorithm too
Non-constructive existence Show it must exist Direct construction hard or unknown
Diagonalization Self-reference / anti-diagonal Counting infinities, undecidability

Read next: