What Is a Mathematical Proof? Why Checking a Million Cases Is Not Enough

A useful illustration is a formula proposed in the eighteenth century that produces a prime number for every value from 0 to 39, which looks convincing until 40, where it fails. Better ones exist. A conjecture of Polya about the distribution of prime factors holds for every number up to nearly a billion and then fails. A statement about two ways of counting primes was shown by Littlewood to reverse at some point, and the first known crossing lies beyond ten to the three hundredth power, a quantity with no physical meaning at all. Because the natural numbers are infinite, no finite search can do more than fail to refute a claim, which is why the word conjecture exists: the Riemann hypothesis has been verified for many billions of cases and remains unproved, and unproved is a real category rather than a formality. The point of a proof is to replace an unbounded search with a finite argument.

A proof is a chain of statements, each of which follows from the axioms of the system, from definitions, or from statements already established, ending at the claim. The axioms are the starting assumptions, taken without proof because a chain of justification must start somewhere, and the choice of them defines which mathematics you are doing, as Euclid's parallel postulate showed when replacing it produced consistent non-Euclidean geometries in the nineteenth century. Rigour means that each step is valid regardless of whether the reader finds the conclusion plausible, and one of the achievements of the twentieth century was showing that any correct proof can in principle be written in a formal language and checked mechanically, which is what proof assistants such as Lean and Coq now do in practice for some major results. Written proofs are not usually formal in that sense, since a fully formal proof of an ordinary theorem runs to thousands of lines, and mathematicians write for other mathematicians at a level of detail that a trained reader can expand.

A handful of argument shapes cover most of what is done:

• •Direct proof: assume the hypothesis and derive the conclusion by a sequence of valid steps
• •Proof by contradiction: assume the statement is false, derive an impossibility, and conclude it must be true. The classic case, that the square root of two cannot be written as a fraction, dates to the Greeks and is still the first one most students meet
• •Proof by contrapositive: instead of showing that if A then B, show that if not B then not A, which is logically equivalent and often much easier
• •Proof by induction: show a statement holds for the first case and that whenever it holds for one case it holds for the next, which establishes it for every case at once, like knocking over an infinite line of dominoes
• •Proof by exhaustion: divide the possibilities into finitely many classes and check them all, which is legitimate when the classes really are finite
• •Constructive proof: demonstrate something exists by building it, as opposed to a proof that shows it must exist without producing one, a distinction some mathematicians regard as essential

Euclid's argument that there is no largest prime is the standard demonstration of what a proof buys. Suppose there were finitely many primes; multiply them all together and add one; the result leaves a remainder of one when divided by any of them, so either it is itself prime or it has a prime factor not on the list; either way the list was incomplete. Two dozen words settle a question about infinitely many numbers permanently. Cantor's diagonal argument shows that the real numbers cannot be listed and so form a larger infinity than the whole numbers, by constructing from any proposed list a number that differs from the first in the first digit, the second in the second, and so on. And the four colour theorem, proved in 1976, was the first major result to depend on a computer checking nearly two thousand configurations, which caused a long argument about whether a proof no human can read in full is a proof at all, an argument that has recovered with the rise of formal verification.

Certainty is the obvious answer and not the whole one. A proof is also an explanation, and mathematicians routinely look for new proofs of theorems already established because a better argument shows why something is true rather than merely that it is, and the why usually generalises. Wiles's proof of Fermat's last theorem in 1994 mattered far less for the original statement, which had no applications, than for the machinery connecting elliptic curves and modular forms that had to be built to reach it, and which is now central to the field. Proofs also fail usefully, since a gap found in an argument frequently identifies the interesting case. And they carry a social dimension that the formal picture omits: a proof becomes accepted when enough qualified readers have checked it, published proofs have turned out to be wrong, and the gap in Wiles's first announcement took a year to repair. Certainty in mathematics is as close to absolute as human knowledge gets, and it is still produced by people reading each other's work.

Checking cases cannot establish a claim about infinitely many numbers, and several conjectures have held for billions of values before failing, so mathematics demands an argument covering every case at once, built from axioms, definitions and previously established results. The standard forms are direct argument, contradiction, contrapositive, induction, exhaustion and construction, and examples such as Euclid on the primes settle infinite questions in a paragraph. Proofs deliver certainty, but they are also explanations, and they are accepted through the judgement of readers.