Appearance
11.5 — Foundations, Infinity, and the Limits of Proof
By 1900 mathematics had a problem it could not ignore. Cantor's infinities (Chapter 1.7) had produced results nobody's intuition could accept. Russell's paradox (Chapter 8.1) had shown that the obvious definition of a set was self-contradictory. Non-Euclidean geometry (Chapter 3.1) had removed the assumption that mathematics describes a unique reality.
The subject that everyone regarded as the most certain form of human knowledge had discovered that it did not know what it was standing on.
This chapter is about the attempt to fix that, and about the discovery that it could not be fixed.
1. Hilbert's programme
At the 1900 International Congress in Paris, David Hilbert presented 23 problems he considered the most important facing mathematics. Several are still open; most that were solved reshaped their fields.
His larger ambition was a programme to place all of mathematics on unshakeable foundations. Reduce every branch to a formal system — a fixed set of axioms plus mechanical rules of inference — and then prove three things about that system:
Consistency. It cannot prove both a statement and its negation. If it could, it would prove everything, and be worthless.
Completeness. Every true statement expressible in the system is provable within it.
Decidability. An algorithm exists that determines, for any statement, whether it is provable.
If all three held, mathematics would be finished as a foundational question. Any dispute could be settled by running a procedure. Hilbert believed it was achievable and that the work was largely a matter of effort.
2. Gödel
In 1931, a 25-year-old Austrian logician named Kurt Gödel published a paper that ended the programme.
The First Incompleteness Theorem. Any consistent formal system powerful enough to express basic arithmetic contains statements that are true but unprovable within it.
The Second Incompleteness Theorem. No such system can prove its own consistency.
The programme was impossible, not merely difficult. Completeness and consistency cannot both be had, and a system cannot certify itself.
How the proof works
The idea is a formalisation of the liar paradox — "this sentence is false" — and its brilliance is in making that self-reference precise inside arithmetic.
Step 1: Gödel numbering. Assign a unique number to every symbol, formula and proof in the system. Now statements about proofs become statements about numbers, and arithmetic can talk about itself.
Step 2: Build the sentence. Construct a formula G whose Gödel-numbered content asserts: "the statement with this number has no proof in this system." G says of itself that it is unprovable.
Step 3: Trap it.
- If G were provable, then it would be false, since it asserts its own unprovability. A system proving a false statement is inconsistent.
- So if the system is consistent, G is not provable.
- But that is exactly what G says. So G is true.
A true statement that the system cannot prove.
And you cannot escape by adding G as a new axiom. The construction runs again in the enlarged system and produces a new unprovable truth. There is no finish line.
What it does and does not mean
Incompleteness is regularly misused, so it is worth being precise.
It does not say mathematics is broken or unreliable. Everything in Parts 1 to 10 of this volume is exactly as solid as it was.
It does not say there are things we can never know. A statement unprovable in one system can be provable in a stronger one. Gödel's own theorem is itself a proof, carried out in a stronger setting.
It does not license "so anything could be true". Gödel proved a precise limitation with a rigorous argument. Using it to justify vagueness inverts its meaning entirely.
What it does say: no single fixed formal system captures all mathematical truth, and mathematics cannot be reduced to a mechanical procedure. Mathematical truth is larger than provability in any one system. That is a genuine philosophical result and it did not stop anyone from doing mathematics.
3. Turing, and decidability
Hilbert's third question — is there an algorithm to decide provability? — was answered in 1936, independently by Alonzo Church and Alan Turing. No.
Turing's route to the answer created computer science. To prove that no algorithm exists, he first had to say precisely what an algorithm is, and he invented the Turing machine for that purpose: an abstract device with a tape, a head, and a table of rules.
He then proved the halting problem unsolvable: no program can determine, for every possible program and input, whether it eventually stops.
The argument is Cantor's diagonal (Chapter 1.7) in a different costume. Suppose a halting-detector H exists. Build a program D that calls H on itself and does the opposite — loops forever if H says it halts, halts if H says it loops. What does D do? Either answer contradicts H. So H cannot exist.
This is the same shape as Gödel's proof, and as Russell's paradox, and as Cantor's diagonal. Four of the deepest results in mathematics and computing are one argument: construct something that refers to itself and does the opposite of what it says.
The practical consequences are severe and permanent. Volume I, 1.7 covers them. No compiler can detect all infinite loops. No antivirus can perfectly classify all programs. No static analyser can prove all interesting properties of arbitrary code. These are not engineering limitations to be overcome; they are theorems.
4. The continuum hypothesis
Chapter 1.7 left this open. Is there an infinity strictly between the countable infinity of the whole numbers and the uncountable infinity of the reals?
Cantor believed not, spent years failing to prove it, and suffered repeated breakdowns partly because of it. It was the first of Hilbert's 23 problems.
Gödel showed in 1940 that it cannot be disproved from the standard ZFC axioms.
Paul Cohen showed in 1963 that it cannot be proved either, using a new technique called forcing that earned him the Fields Medal.
So the question is undecidable. Both answers are consistent with the standard axioms. You may add either as a new axiom and get a coherent mathematics.
This is a fundamentally different situation from an unsolved problem. The Riemann Hypothesis is presumably true or false and we do not know which. The continuum hypothesis has no answer within the accepted framework. It is a place where mathematics genuinely branches, in the same way geometry branched when the parallel postulate turned out to be optional.
5. What mathematics is, then
The foundational crisis produced several positions on what mathematical objects actually are, and mathematicians hold them inconsistently and mostly without noticing.
Platonism. Mathematical objects exist independently of us, and we discover rather than invent them. Gödel held this strongly, and it is what most working mathematicians believe when they are doing mathematics rather than talking about it — the feeling that a proof was found rather than made is very hard to shake.
Formalism. Mathematics is the manipulation of symbols according to rules, with no claim about what the symbols refer to. Hilbert's position, and incompleteness damaged it badly.
Intuitionism. Only constructions count. Brouwer rejected proof by contradiction for existence claims — showing that "no such object exists" is contradictory does not show you where the object is. This position rejects some standard mathematics and, unexpectedly, turned out to matter enormously in computer science, where a constructive proof is a program. The Curry–Howard correspondence makes this precise: proofs and programs are the same thing, and it is the basis of proof assistants and dependently typed languages.
Structuralism. Mathematics studies structures, and what the objects "are" is not a meaningful question — only their relationships matter. The number 3 is not a particular set; it is whatever plays the role of 3.
The honest position is that nobody has settled this, and that mathematics works regardless. That is itself worth noticing: a field can be the most reliable thing humans do while its practitioners disagree about what it is about.
6. The unreasonable effectiveness
Eugene Wigner's 1960 essay asked a question that has no good answer: why does mathematics work so well for describing the physical world?
The examples are startling.
Non-Euclidean geometry was invented in the 1830s by changing an axiom for the sake of it, and turned out in 1915 to be the geometry of spacetime.
Complex numbers were forced on mathematics by cubic equations in the 1500s, and turned out to be essential to quantum mechanics.
Group theory came from a dying twenty-year-old's analysis of polynomial equations, and became the language of particle physics — the Standard Model is literally a statement about which symmetry groups are involved.
Riemannian geometry, matrices, Hilbert spaces, fibre bundles — the mathematics was always there first, developed for internal reasons, and the physics found it waiting.
Possible explanations, none fully satisfying. Perhaps we only notice the hits, and the vast body of mathematics with no application is forgotten. Perhaps mathematics is abstracted from physical experience, so its applicability is unsurprising. Perhaps evolution shaped minds that find nature's actual patterns natural. Perhaps the universe is mathematical in some deep sense.
Wigner's own conclusion was that it is a gift we neither understand nor deserve, and that we should be grateful and hope it continues to hold.
7. Where this leaves you
Mathematics is not a body of certain truths handed down. It is the most reliable thing humans have ever built, and it is built, and it has limits that were proved from inside it.
- Some true statements cannot be proved.
- Some questions have no answer within the standard framework.
- Some problems have no algorithm.
- No system can guarantee its own soundness.
And none of it stops anything. Every result in this volume remains exactly as usable. The bridges stand, the encryption holds, the forecasts are made, the models train.
What the foundational story gives you is the correct relationship to the subject: not faith, but understanding of what is being claimed and on what basis. Every theorem here rests on stated assumptions and a chain of reasoning you could in principle check. That is a stronger position than certainty, because it is honest about its own footing.
That is Volume II. You began with a shepherd matching pebbles to sheep and ended with the proof that mathematics cannot certify itself — and everything between is a tool you can now pick up.
The mathematics in this volume feeds directly into what follows. Volume III uses the differential equations of Part 6 and the transforms of Part 9 on every page. Volume IV cannot start without the calculus of Part 5. Volume V's medical statistics are Part 7. And Volume I, which you have already read, leaned on Parts 4, 5, 7 and 8 throughout.
None of it is a prerequisite you have to fear any more.
Every formula above, built from scratch
None of the results in this chapter are worth memorising, because each one can be rebuilt in under a minute from something simpler. What follows is that rebuilding, one result at a time, so the formula and the reason for it sit on the same page as the explanation that needed them.
Gödel's incompleteness theorems
First theorem. Any consistent formal system strong enough to express ordinary arithmetic contains true statements it cannot prove.
Second theorem. No such system can prove its own consistency.
The idea of the proof, which is a diagonal argument. Gödel found a way to encode statements about arithmetic as statements of arithmetic — every formula and every proof gets a number, now called its Gödel number. With that machinery he constructed a sentence G that, decoded, says:
"This statement has no proof in this system."
Now reason about G. If the system could prove G, then G would be false — but a consistent system does not prove false things. So G is unprovable. And that is precisely what G asserts, so G is true and unprovable.
What it did and did not destroy. It ended Hilbert's programme of putting all mathematics on a complete, mechanically verifiable foundation. It did not show mathematics is unreliable, or that there are things humans can know and machines cannot, or anything about consciousness — three claims made constantly and supported by nothing in the proof. It showed that truth and provability are different things, and the gap cannot be closed from inside.
Turing's halting problem, published five years later, is the same argument in the language of computation, and it is why no program can decide whether an arbitrary program stops.
More places these turn up
Euler's theorem is running inside the padlock on your browser right now. Stirling's approximation sets the theoretical floor on how fast any sorting algorithm can be, which is why nothing beats n\log n by comparison alone. The Gaussian integral is why the bell curve's formula has \sqrt{2\pi} in it, which puts it inside every statistical claim you read. The prime number theorem is why your bank can generate a fresh key in a second. And Gödel's theorem is the reason no compiler can warn you about every possible infinite loop — not because compilers are not clever enough, but because it has been proved that none ever can be.
Next: 11.P — Worked Problems works these famous results with real numbers, so they stop being quotations and become things you have done.