Mathematical proof
A mathematical proof refuses to settle for examples. You can show a hundred cases where a statement holds, a thousand, a million, and a mathematician will still shake their head. A proof must demonstrate that the statement is true in all possible cases, not merely the ones anyone has bothered to check. This is the strange demand at the heart of the subject. It separates logical certainty from what proof writers dismiss as mere reasonable expectation. A proof is a deductive argument that shows the stated assumptions logically guarantee the conclusion. So where did this uncompromising idea come from? Why does the word for it trace back to a Latin verb meaning to test? And what happens when a proof grows so long that no human can read it, and a machine must check the work instead? The story runs from ancient Greek land surveyors to a hypothetical tome that the mathematician Paul Erdos called The Book.
The word proof descends from the Latin probare, meaning to test. That single root scattered across languages and meanings. English kept probe, probation, and probability. Spanish took probar, which can mean to taste, sometimes to touch or to test. Italian gave provare, to try, and German probieren, also to try. The shared thread is the act of putting something to the test before trusting it. The legal world borrowed the same idea through the term probity, meaning authority or credibility. Probity names the power of testimony to prove facts when those facts are spoken by persons of reputation or status. Long before anyone wrote a strict proof, people leaned on plausibility arguments built from heuristic devices like pictures and analogies. The notion of actually demonstrating a conclusion likely first appeared in geometry, a field that grew out of the practical problem of measuring land.
Thales, who lived from 624 to 546 BCE, gave some of the first known proofs of theorems in geometry. Hippocrates of Chios, born around 470 BCE, did the same. Others stopped short of that final step. Eudoxus, who lived from 408 to 355 BCE, and Theaetetus, from 417 to 369 BCE, formulated theorems but did not prove them. Aristotle, living from 384 to 322 BCE, contributed a rule about language itself. He held that definitions should describe a concept in terms of other concepts already known. Euclid, working around 300 BCE, introduced the axiomatic method still in use today. The method begins with undefined terms and with axioms, propositions about those terms assumed to be self-evidently true. The word axiom comes from the Greek axios, meaning something worthy. From that foundation, deductive logic proves the theorems. Euclid's Elements was read by anyone considered educated in the West until the middle of the 20th century. Beyond the Pythagorean theorem, it ventured into number theory, with a proof that the square root of two is irrational and a proof that the primes never run out.
Al-Hashimi, an Iraqi mathematician of the 10th century, treated numbers as objects in their own right. He called them lines, but he did not tie them to measurements of geometric figures. Working this way, he proved algebraic propositions about multiplication, division, and more, including the existence of irrational numbers. Al-Karaji pushed the toolkit further in a work called the Al-Fakhri, dated to the year 1000. There he introduced an inductive proof for arithmetic progressions. He used that method to prove the binomial theorem and to establish properties of Pascal's triangle. Modern proof theory took a more radical turn. It treats proofs as inductively defined data structures and drops any requirement that axioms be true in some deeper sense. That move opened the door to parallel theories built on alternate sets of axioms, such as axiomatic set theory and non-Euclidean geometry.
A working proof is written in natural language, a rigorous argument meant to convince an audience that a statement is true. The standard of rigor is not absolute and has shifted throughout history. The same result can be presented differently depending on who is meant to follow it. To win acceptance, a proof must meet communal standards of rigor, and an argument judged vague or incomplete may simply be rejected. The field of mathematical logic formalizes all of this. A formal proof abandons natural language for a formal language. It is a sequence of formulas, beginning with an assumption, where each formula is a logical consequence of the ones before. Proof theory then studies these formal objects. Its most famous and surprising finding is that almost all axiomatic systems can generate undecidable statements, ones not provable within the system. The belief that any published proof could, in principle, be converted into a formal proof is rarely tested. Outside automated proof assistants, the conversion is hardly ever done.
Proofs can be admired for their mathematical beauty. Paul Erdos described the proofs he found especially elegant as coming from The Book, a hypothetical tome holding the most beautiful method of proving each theorem. That image became real in print. The book Proofs from THE BOOK, published in 2003, gathers 32 proofs its editors find particularly pleasing. Philosophy circles back to a stubborn question about what proofs even are. A classic debate asks whether mathematical proofs are analytic or synthetic. Kant, who introduced the analytic-synthetic distinction, held that mathematical proofs are synthetic. Quine pushed back in his 1951 essay Two Dogmas of Empiricism, arguing that the distinction itself cannot be sustained.
Direct proof combines axioms, definitions, and earlier theorems to reach a conclusion, as when two even integers written as 2a and 2b sum to 2 times the quantity a plus b, and so are even. Proof by mathematical induction, despite its name, is a method of deduction, not inductive reasoning. It proves a single base case and an induction rule, so that one case implies the next and all cases follow. A variant called proof by infinite descent can establish the irrationality of the square root of two. Proof by contraposition replaces the claim if p then q with its logical equivalent, if not q then not p. Proof by contradiction, known in Latin as reductio ad absurdum, assumes a statement true and derives a logical contradiction, forcing the statement to be false. Proof by construction builds a concrete example, the way Joseph Liouville proved transcendental numbers exist by writing one down explicitly. Proof by exhaustion splits a claim into finitely many cases and checks each, and the number of cases can grow enormous. A combinatorial proof shows two expressions count the same object in different ways, often through a bijection or a double counting argument. A nonconstructive proof shows an object exists without showing how to find it. A probabilistic proof uses probability theory to show, with certainty, that an example exists, which is not the same as arguing a theorem is probably true. Plausibility can sit far from genuine proof, as the work on the Collatz conjecture and the disproof of the Mertens conjecture both reveal.
The first proof of the four color theorem ran to 1,936 cases, and it was controversial because most of those cases were checked by a computer program rather than by hand. Until the twentieth century, people assumed any proof could in principle be verified by a competent mathematician. Automated theorem provers and proof assistants changed that. They now handle theorems and calculations too long for any human or team of humans to check. Some mathematicians worry that an error in the program, or a run-time error during its calculations, throws the validity of such results into doubt. The risk can be lowered with redundancy, self-checks, and multiple independent approaches and programs. Human-checked proofs carry their own hazard, especially when natural language hides assumptions and fallacies that only deep insight can expose. Some statements escape proof entirely. The parallel postulate is neither provable nor refutable from the rest of Euclidean geometry. Godel's first incompleteness theorem shows that many axiom systems of interest will contain undecidable statements. When a proof does reach its end, a writer may close with Q.E.D., short for the Latin quod erat demonstrandum, that which was to be demonstrated, or mark it with a small square called a tombstone, after the mathematician Paul Halmos. Unicode even reserves a character for the moment, U+220E, the end of proof mark.
Up Next
Common questions
What is a mathematical proof?
A mathematical proof is a deductive argument for a mathematical statement, showing that the stated assumptions logically guarantee the conclusion. It must demonstrate that the statement is true in all possible cases, not merely in many examples, which separates it from empirical or inductive reasoning that only establishes reasonable expectation.
Where does the word proof come from in mathematics?
The word proof derives from the Latin probare, meaning to test. Related words include English probe, probation, and probability, along with Spanish probar, Italian provare, and German probieren, all carrying the sense of testing or trying.
Who developed the axiomatic method of mathematical proof?
Euclid, working around 300 BCE, introduced the axiomatic method still in use today. It begins with undefined terms and axioms assumed to be self-evidently true, then proves theorems from that basis using deductive logic. His work Elements was read by educated people in the West until the middle of the 20th century.
What are the main methods of mathematical proof?
The main methods include direct proof, proof by mathematical induction, proof by contraposition, proof by contradiction, proof by construction, proof by exhaustion, combinatorial proof, nonconstructive proof, and probabilistic proof. Each establishes a conclusion in a different way, from combining earlier theorems to constructing an explicit example.
Why is the proof of the four color theorem controversial?
The first proof of the four color theorem was a proof by exhaustion with 1,936 cases. It was controversial because the majority of those cases were checked by a computer program rather than by hand, raising concern that a program error or run-time error could call its validity into question.
What does Q.E.D. mean at the end of a mathematical proof?
Q.E.D. stands for the Latin quod erat demonstrandum, meaning that which was to be demonstrated, and it marks the end of a proof. A common alternative is a small square or rectangle called a tombstone or Halmos, after Paul Halmos, and Unicode provides the end of proof character U+220E.
All sources
27 references cited across the entry
- 1webOne of the Oldest Extant Diagrams from EuclidBill Casselman — University of British Columbia
- 2bookThe Concise Oxford Dictionary of Mathematics, Fourth editionClapham, C. et al.
- 3bookThe Nuts and Bolts of Proofs: An Introduction to Mathematical ProofsAntonella Cupillari — Academic Press — 2005
- 4bookDiscrete Mathematics with ProofEric Gossett — John Wiley & Sons — July 2009
- 6bookThe Emergence of Probability: A Philosophical Study of Early Ideas about Probability, Induction and Statistical InferenceIan Hacking — Cambridge University Press — 1984
- 7bookThe development of logicWilliam Kneale et al. — Oxford University Press — May 1985
- 8webThe genesis of proof in ancient Greece The pedagogical implications of a Husserlian readingAndreas Moutsios-Rentzos et al. — February 2015
- 9bookAn Introduction to the History of Mathematics (Saunders Series)Howard W. Eves — Cengage — January 1990
- 10citationThe Theory of Quadratic Irrationals in Medieval Oriental MathematicsGalina Matvievskaya — 1987
- 11citationHandbook of Proof TheorySamuel R. Buss — Elsevier — 1998
- 12webTwo Dogmas of EmpiricismWillard Van Orman Quine — 1961
- 15bookMathematik für das Bachelorstudium I: Grundlagen und Grundzüge der linearen Algebra und AnalysisMatthias Plaue et al. — Springer-Verlag — 2019-02-11
- 16bookMathematik für Informatiker: Grundlagen und AnwendungenWerner Struckmann et al. — Springer-Verlag — 2016-10-20
- 17webCombinatorial ProofsSinho Chewi
- 18webNonconstructive ProofEric W. Weisstein
- 23bookIndra's Pearls: The Vision of Felix KleinDavid B. Mumford et al. — Cambridge University Press — 2002
- 25bookIntroducing Fractal GeometryNigel Lesmoir-Gordon — Icon Books — 2000
- 26journalEstablishing a Custom of Proving in American School Geometry: Evolution of the Two-Column Proof in the Early Twentieth CenturyPatricio G. Herbst — 2002
- 27webIntroduction to the Two-Column ProofDr. Fisher Burns