The Limits of the Rules
The first essay ended with a division of labour: we choose the rules, we discover what follows. In September 1930 a twenty-four-year-old showed that what follows can outrun any rulebook, and in 1963 another mathematician showed that some questions do not follow at all. Whether that helps the Platonist or the formalist is still being argued.
On 8 September 1930, David Hilbert gave a radio address in Königsberg to the Society of German Scientists and Physicians.[1] He was sixty-eight, the most influential mathematician alive, and he had spent the previous decade on a programme meant to put the whole of mathematics beyond doubt: write down the axioms, treat proofs as finite strings of symbols, and prove by strictly finite means that the strings could never lead to a contradiction. He closed the address with four words that are now carved on his tombstone in Göttingen. Wir müssen wissen. Wir werden wissen. We must know. We will know.
The day before, in a discussion session at a smaller conference in the same city, a doctoral graduate from Vienna named Kurt Gödel had mentioned, almost as an aside, that one could write down statements about whole numbers that were true but could not be proved in the system of Principia Mathematica or in any comparable one. Almost nobody in the room registered what he had said. John von Neumann did. He cornered Gödel afterwards, went home, and within weeks had worked out a consequence Gödel already had in hand: no such system can prove its own consistency either. Hilbert's programme, in the form Hilbert had stated it, was over before his speech had finished echoing.
The previous essay argued that the most defensible account of mathematics divides the labour: what we invent are the rules — the definitions, the axioms, the notation — and what we discover is what follows from them, over which we have no authority at all. Bombelli chose to extend the number system; he did not choose that the extension would be unique. That position sounds like a settlement, and it is not, because it assumes that “what follows from the rules” is a well-behaved notion. Gödel showed it is larger than anything the rules can reach. Paul Cohen, in 1963, showed that for some questions it is empty. This essay is about what those two results do to the settlement.
A sentence that describes its own fate
Hilbert's idea was that mathematics could be made safe by treating it as a game. Fix a finite alphabet, a list of axioms, and a list of rules for deriving new strings from old ones. Then everything — the infinite, the transfinite, Cantor's paradise, which Hilbert had promised in 1926 nobody would expel us from — reduces to bookkeeping about finite objects, and the bookkeeping can be checked.[1] What remained was to prove, in that same finite spirit, that the game could not produce both a statement and its negation.
Gödel's move was to notice that bookkeeping about finite strings is itself arithmetic. Assign a number to every symbol, hence to every formula, hence to every proof. The statement “the string with number n is provable in this system” then becomes a statement about whole numbers — a complicated one, but of the same kind as “n is prime”. And once the system can talk about its own provability in the language of arithmetic, it can be made to talk about itself. Gödel constructed a sentence, call it G, which under the numbering says precisely this:
Suppose the system proves G. Then G is false, and the system has proved a falsehood — it is inconsistent. Suppose instead the system is consistent. Then it does not prove G; but that is exactly what G asserts, so G is true. A consistent system rich enough to do arithmetic therefore contains a true sentence it cannot prove. That is the first incompleteness theorem.[2] The second is a corollary that hurt more: the sentence “this system is consistent” can also be written in arithmetic, and it turns out to be equivalent to G. So a consistent system cannot prove its own consistency. Hilbert had asked for a finitary consistency proof of arithmetic; arithmetic itself, and anything containing it, cannot supply one.
There is a loophole, and it matters for what comes later. G is unprovable in the system that generated it, but it is trivially provable in that system plus G as a new axiom, and in any sufficiently stronger system. The catch is that the stronger system has its own Gödel sentence, and so on without end. Gerhard Gentzen made the price precise in 1936: the consistency of ordinary arithmetic can be proved, but only by assuming a principle of induction along the infinite ordinal ε0 — a form of reasoning that is not itself finitary.[3] You can certify the finite, but only by borrowing from the infinite, and the loan is never fully repaid.
What incompleteness does to the two positions
The theorem has been recruited by both sides ever since, and it is worth being clear about what each recruitment actually claims.
The common ground is larger than either camp likes to say. Whatever “true but unprovable” ultimately means, nobody since 1931 can identify mathematics with the set of consequences of a fixed list of rules. That was Hilbert's hope and the purest form of the constructivist position, and it is gone. The formalist keeps a weaker claim: mathematics is what follows from rules, but the rules are open-ended, and choosing the next one is part of the practice. The realist keeps a weaker claim too: the choosing is not arbitrary, because something is constraining it. The argument has moved up a level, from “are the consequences found or made?” to “are the rules?”
A statement about counting that counting cannot reach
The standard complaint about Gödel sentences is that they are contrived. G is a self-referential trick; it says nothing about numbers anyone would ever care about; the theorem is a curiosity about the edge of the map. The complaint was reasonable for about fifty years, and then it stopped being available.
In 1944 Reuben Goodstein defined a sequence. Take a whole number and write it in hereditary base 2 — base 2, with the exponents also written in base 2, and their exponents, all the way down. Now do two things: change every 2 in the expression to a 3, and subtract 1. Write the result in hereditary base 3, change every 3 to a 4, subtract 1. Continue. The sequence starting from 3 is short enough to follow by hand:
Six terms, then it hits zero. Now start from 4 instead. The sequence runs 4, 26, 41, 60, 83, 109, and keeps climbing; the base-changing step is a far stronger push upward than the subtraction is downward, and for a very long time the numbers simply grow. It does reach zero. It reaches zero after 3 · 2402,653,211 − 2 steps, a number with something over 121 million decimal digits.
Goodstein proved that every such sequence, from every starting point, terminates.[6] The proof is short and beautiful and does something odd: it replaces the base, at each step, with the infinite ordinal ω. The base-changing operation then does nothing to the ordinal, the subtraction strictly decreases it, and a strictly decreasing sequence of ordinals cannot go on forever. The finite sequence is tamed by mapping it into the transfinite and watching it fall.
In 1982 Laurie Kirby and Jeff Paris proved that this is not an accident of Goodstein's method.[7] Goodstein's theorem cannot be proved in Peano arithmetic at all. The theorem is equivalent, over the standard axioms of arithmetic, to the well-ordering of ε0 — the very principle Gentzen had needed for consistency. So here is a statement about nothing but whole numbers, with no self-reference and no encoding, which every mathematician accepts as true, which children can be taught to compute, and which the standard axioms for the whole numbers cannot decide. Five years earlier, Paris and Leo Harrington had found another, a modest-looking variant of Ramsey's theorem about colouring finite sets.[7] These are not the edge of the map. They are a few streets from the centre.
Whatever you think Gödel's G is about, Goodstein's theorem is about counting. And it is either a piece of the furniture of reality that the rules of arithmetic happen not to mention, or a consequence of a slightly larger game than the one you thought you were playing. What it is not, on any reading, is a consequence of the rules you wrote down.
The parallel postulate, again
Mathematics had been here before, and the earlier episode is worth having in mind for what comes next, because it has exactly the shape of what Cohen would find in set theory.
Euclid's fifth postulate says, in effect, that through a point not on a line there is exactly one parallel to that line. It is longer and less obvious than the other four, and for two thousand years mathematicians tried to derive it from them. Girolamo Saccheri spent a book on it in 1733 and believed he had succeeded. Gauss worked it out privately from about 1817 and told no one, writing to Bessel in 1829 that he feared the clamour of the Boeotians. Nikolai Lobachevsky published in 1829 and János Bolyai in 1832 — as an appendix to his father's textbook — that a perfectly consistent geometry exists in which there are infinitely many parallels through the point.[8] Gauss's reply to Bolyai's father was that he could not praise the work, because to praise it would be to praise himself.
Eugenio Beltrami settled the matter in 1868 by building the new geometry inside the old: a model of Lobachevsky's plane out of ordinary Euclidean objects, so that any contradiction in the one would be a contradiction in the other.[8] The fifth postulate was therefore independent of the first four: consistent with them, and so was its negation. There was no fact of the matter about parallels that the other axioms could deliver, and the choice of which geometry to work in was, from inside mathematics, free.
Then physics chose. Riemann's 1854 lecture had generalised the whole business to curved spaces of any dimension, with no application in view; in 1915 Einstein found that the geometry of the physical world is Riemannian and that the curvature is what we had been calling gravity. Immanuel Kant had held, in 1781, that Euclidean geometry was neither discovered outside us nor invented by us, but was the form of our spatial intuition, known with certainty in advance of experience — the third classical position, alongside Platonism and empiricism, and for a century the dominant one.[9] Non-Euclidean geometry did not refute Kant by itself; a consistent alternative is not a true one. General relativity did the rest. The form of our intuition turned out to be one option among several, and not the one the universe took.
Cantor's paradise and the door nobody can open
Georg Cantor proved in 1874 that there are more real numbers than whole numbers — not more in the sense of a longer list, but more in the sense that no list can contain them.[10] In 1891 he gave the argument that is now taught to first-year students: any proposed enumeration of the reals can be used to construct a real not on it. Infinity came in sizes. The size of the whole numbers he called ℵ0; the size of the continuum, the real line, is 2ℵ0, strictly larger.
The reaction was not universally warm. Leopold Kronecker, who controlled the leading German journal, delayed and disparaged Cantor's papers, and is reported by Heinrich Weber to have said in an 1886 lecture that the whole numbers were made by God and everything else is the work of man.[11] It is the constructivist position in a single sentence, and Kronecker meant it: he did not believe the reals, as Cantor conceived them, existed to be counted.
Cantor's own question was simpler and harder. Is there any size of infinity strictly between the whole numbers and the continuum? He believed not — that the continuum is the very next size up — and this is the continuum hypothesis. He could not prove it. Hilbert placed it first on his list of twenty-three problems for the twentieth century, in Paris in 1900.[1]
The answer came in two halves. In 1938 Gödel showed that the continuum hypothesis is consistent with the standard axioms of set theory, by constructing a universe — the constructible universe, L — in which the axioms hold and so does the hypothesis.[12] In 1963 Paul Cohen, a young analyst at Stanford with no background in logic, invented a technique called forcing and used it to build universes in which the axioms hold and the hypothesis fails.[13] He was given the Fields Medal in 1966, the only one ever awarded for work in logic. Put together: the standard axioms of mathematics do not decide whether there is a size of infinity between the integers and the reals. Beltrami's independence, a century on, at the foundations of everything.
One universe or many
Gödel did not think the matter was closed. In a 1947 essay, What is Cantor's continuum problem?, he argued that independence from our current axioms says nothing about truth: the axioms describe a well-determined reality, our description is incomplete, and new axioms — ones that would, in his phrase, force themselves upon us as true — would eventually settle the question. He expected the hypothesis to be false.[12] So did Cohen, who suspected the continuum was far larger than anyone had guessed.
Eighty years on, the question is open, and the state of the argument is instructive. Hugh Woodin, the leading set theorist of the realist school, argued through the 2000s that the hypothesis is false, on the strength of a logic he developed for the purpose; since around 2010 he has pursued a different programme, an inner model he calls Ultimate L, on which it would be true.[14] When the field's most committed Platonist has changed his expected answer, you have a fair measure of how far the evidence is from deciding.
Joel David Hamkins made the opposite move in 2012.[15] Forcing, he observed, does not merely show that two answers are consistent; it lets us build and inhabit universes with each answer, and our mathematical experience inside them is as rich and as vivid as in any other. On his multiverse view the continuum hypothesis is not open but settled: we know precisely how it behaves — true in these universes, false in those — and asking whether it is really true is like asking whether the parallel postulate is really true. Solomon Feferman had said something similar in a different register: the hypothesis is inherently vague, not a definite mathematical problem at all, because the notion of an arbitrary subset of an infinite set is not one we ever fully specified.[5]
The realist has one card left, and it is a good one. Since Gödel, set theorists have studied a hierarchy of large cardinal axioms — ever stronger assertions that very large infinities exist. There is no reason these should be comparable to one another. They arise from different intuitions, in different decades, for different purposes. Yet as an empirical matter, every natural large cardinal axiom anyone has proposed turns out to sit on a single linear scale of consistency strength: for any two, one implies the consistency of the other.[16] Theories from completely separate areas of mathematics — analysis, combinatorics, the theory of definable sets of reals — are calibrated, exactly, against the same ladder. Nobody designed this. Nobody can explain it. It is Frobenius's three division algebras again: a constraint that appears where the constructivist would predict freedom, and that reads, from inside the practice, like the outline of something.
Choosing again
The division of labour survives, but it is no longer a single act. We choose rules; we discover consequences; we hit a question the rules leave open; we choose again. Gödel showed that the consequences of any rulebook include truths the rulebook cannot reach, so “what follows” is always larger than “what is derivable”. Cohen showed that some questions are not consequences at all — that a rulebook adequate for all of working mathematics can be silent about whether there is an infinity between the integers and the line. In both cases the mathematician is handed the choosing back.
Whether the choosing tracks something is the same question as before, one level up. Gödel and Woodin believe the new axioms are discovered: that the right ones will force themselves on us the way the complex numbers eventually did, unique and unavoidable. Hamkins believes the choice is genuinely free and the multiverse is the whole story. Realism, on this view, has become a bet on convergence — on whether mathematicians a century from now will have settled on one set theory the way their predecessors settled on one arithmetic. The well-ordering of the large cardinals is the evidence for the bet. The eighty-year stalemate over the continuum is the evidence against.
Hilbert's tombstone says we will know. Gödel's theorem says: not all of it, and not from any single vantage point. Cohen's says: for some questions there may be nothing to know until we decide, and the deciding — however much it feels like discovery from the inside — is ours to do. What has not changed since Bombelli is that once we decide, the consequences are not.
The next essay turns from what can be proved to what proving has become — because since 1976 the answer to “who checked it?” has increasingly been: nobody, and a machine.
Where this could go
The Big Five. Reverse mathematics finds that nearly every theorem of ordinary mathematics, when you ask exactly which axioms it needs, lands on one of five levels — not a continuum of strengths but five discrete rungs. Like the linear ordering of the large cardinals, this is an observed regularity with no accepted explanation, and it is more accessible than the set-theoretic case because the theorems involved are ones every mathematician knows.
Independence leaking into ordinary mathematics. The continuum hypothesis looks remote until it turns up in a question about abelian groups. Shelah showed in 1974 that the Whitehead problem, a natural question in algebra, is independent of the standard axioms; Kaplansky's conjecture in Banach algebras and the Borel conjecture in measure theory are the same kind of case. A tour of these would show the multiverse reaching into rooms where working mathematicians live.
Ultimate L, as of now. Woodin's programme is the one live attempt to settle the continuum from a realist position, and its status changes. Koellner's Stanford Encyclopedia entries track it. An essay that explained what an inner model is, why one might settle the continuum, and what Woodin has and has not proved would be the natural sequel to this one's stalemate section.
Could physics choose an axiom? Non-Euclidean geometry was decided by Einstein. Set theorists mostly hold that nothing physical could ever bear on the size of the continuum. The argument for that is worth examining rather than assuming, and there is a minority literature — on whether spacetime is a continuum at all, on infinities in physical theories — that takes the other side seriously.
A different foundation. Vladimir Voevodsky's univalent foundations, built in the 2010s on homotopy type theory, treat equality as structural — two things are equal when there is an equivalence between them — which makes structuralism a feature of the formalism rather than a philosophy about it. It is also the native language of the proof assistants in the next essay. The two threads meet there.
This piece was written collaboratively with Claude Fable 5.1 (Anthropic): human specification, editorial direction and critical review; machine synthesis, drafting and figure generation. It is Part II of Found or Made.
The figure is honest in its two hard panels and schematic in its easy one: the arcs in the Poincaré disc are computed geodesics (circles meeting the boundary at right angles, through the same point, none crossing the line), while the sphere is a drawing. The Goodstein sequence from 3 was computed by hand; the figure of 3 · 2402,653,211 − 2 steps from 4 is the published value, not recomputed here.
Contested positions are labelled as such: Woodin's change of expected answer on the continuum hypothesis is summarised from his published papers, not from private communication; Hamkins' multiverse and Gödel's realism are presented as an open dispute; the linear ordering of the large cardinals by consistency strength is an observed regularity with no theorem behind it, and the text says so. The Kronecker remark comes to us through Weber's obituary, not from Kronecker's pen.
Nothing here settles anything. The essay's claim is only that the settlement in Part I — rules chosen, consequences found — has to be made iterative, and that both camps can accept that much.
Authored by: Luis Matos Ferreira — Physicist, Developer, Writer
- Invented, Then Unavoidable — imaginary numbers, rigidity, and why physicists trust beauty.
- The Limits of the Rules — Gödel, Goodstein, the continuum, and what happens when the axioms run out. This essay.
- What a Proof Is Now — Lakatos, the four colour theorem, Lean, and proofs no one has read.
- Where Number Comes From — the number sense, cultures without counting, and whether aliens would share our arithmetic.
- The Bus at Coutances — how mathematicians and physicists actually think: images, incubation, birds and frogs, and minds without pictures.
- Hilbert, “Mathematische Probleme”, Paris, 1900; “Über das Unendliche”, 1926; Königsberg address, 8 September 1930.
- Gödel, “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I”, 1931.
- Gentzen, “Die Widerspruchsfreiheit der reinen Zahlentheorie”, 1936; Rosser, “Extensions of some theorems of Gödel and Church”, 1936.
- Gödel, Gibbs lecture, 1951, in Collected Works III, 1995; Lucas, “Minds, Machines and Gödel”, 1961; Penrose, The Emperor's New Mind, 1989.
- Feferman, Friedman, Maddy & Steel, “Does mathematics need new axioms?”, Bulletin of Symbolic Logic, 2000.
- Goodstein, “On the restricted ordinal theorem”, 1944.
- Paris & Harrington, “A mathematical incompleteness in Peano arithmetic”, 1977; Kirby & Paris, “Accessible independence results for Peano arithmetic”, 1982.
- Lobachevsky, “On the Principles of Geometry”, 1829; Bolyai, Appendix, 1832; Beltrami, “Saggio di interpretazione della geometria non-euclidea”, 1868.
- Kant, Critique of Pure Reason, 1781.
- Cantor, “Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen”, 1874; diagonal argument, 1891.
- Weber, “Leopold Kronecker”, Jahresbericht der DMV, 1893 (source of the Kronecker remark, 1886).
- Gödel, The Consistency of the Continuum Hypothesis, 1940; “What is Cantor's continuum problem?”, 1947, revised 1964.
- Cohen, “The independence of the continuum hypothesis”, PNAS, 1963–64; Set Theory and the Continuum Hypothesis, 1966.
- Woodin, “The Continuum Hypothesis, Parts I and II”, Notices of the AMS, 2001; “Strong axioms of infinity and the search for V”, 2010.
- Hamkins, “The set-theoretic multiverse”, Review of Symbolic Logic, 2012.
- Koellner, “Large Cardinals and Determinacy”, Stanford Encyclopedia of Philosophy.
Comentários
Enviar um comentário