Jumping out of the System

A formal system has been shown to leave one sentence unsettled, and the sentence happens to be true. The obvious response is to bolt it on: write the missing sentence into the axiom list and carry on. The most important thing to understand about Chapter XV is that this repair works exactly once, produces a genuinely stronger system, and leaves the system exactly as incomplete as before — because the repaired system satisfies the same hypotheses and therefore has a new missing sentence of its own.

Here is the sentence being bolted on, reconstructed in three sentences so that nothing has to be looked up. Typographical Number Theory, or TNT, is Hofstadter's name for a formal system whose strings talk about the natural numbers and whose only notion of correctness is "derivable from the axioms by the rules". Every string of TNT can be given a number by a mechanical code, so claims about TNT's strings become claims about arithmetic, which TNT already discusses; feeding a formula its own code number produces G, a sentence that says of itself that it is not derivable in TNT. If TNT is consistent then G cannot be derived — and that is precisely what G asserts, so G is true of the natural numbers while sitting outside TNT's reach.

Today's boundary is narrow and worth stating up front. Inside: what happens when G is added as an axiom, what happens when its denial is added instead, what kind of mathematical object the second branch produces, what Hilbert wanted and what Gentzen delivered, and who exactly performs the "jump" of the chapter's title. Outside: any new proof machinery — nothing today needs a construction that Chapter XIV did not already supply — and any claim that a mind is or is not a machine, which appears here only to have its supporting argument dismantled.

The first three boxes are the machine as it has been described throughout this course: a supply of strings, a derivation process, and the strings that come out of it. Today's addition is the right-hand pair. Bolting G on is a real operation that produces a real, different system, and that system's own missing sentence is the new object this chapter is about.

Adding an axiom is not a patch to an existing machine; it defines a different machine, and the only honest way to ask whether the repair worked is to check the new machine against the theorem's hypotheses one at a time. The theorem applies to a system that is consistent, effectively axiomatized, and strong enough to express elementary arithmetic. Call the repaired system TNT₁, whose axioms are TNT's five axioms together with G.

Consistent. G is true of the natural numbers, and TNT's axioms are true of them too, so the ordinary whole numbers satisfy every axiom of TNT₁. A system with a model cannot derive a contradiction, so TNT₁ is consistent. This argument uses more than bare consistency of TNT — it uses the fact that TNT's theorems are actually true of the numbers — and that extra assumption will matter later when the other branch is taken.

Effectively axiomatized. This is the condition that looks like bookkeeping and is not. A system is effectively axiomatized when there is a mechanical procedure that, handed any string, decides whether it is an axiom. TNT₁'s procedure is TNT's procedure with one extra comparison: is this string G? One extra comparison is still mechanical, so the property survives, and so does everything built on it — the coding of derivations as numbers, the proof-pair relation, the whole arithmetization.

Strong enough. TNT₁ contains all of TNT, so anything TNT could express, TNT₁ can express. Strength only ever goes up when axioms are added.

All three hypotheses hold. So the construction from Chapter XIV can be run again, unchanged, on TNT₁: code its strings, define its proof-pair relation, build the formula asserting non-derivability in TNT₁, and arithmoquine it. The result is G₁, saying "G₁ is not a theorem of TNT₁". It is undecidable in TNT₁ and true of the natural numbers, for the same reasons and by the same argument.

One detail settles the obvious objection that nothing new has happened. G₁ is not G. TNT₁ derives G in one line, because G is one of its axioms; G₁ it cannot derive at all. The repair did close the hole it was aimed at. It simply opened another one.

Saying "the tower never ends" is an assertion until the rungs are named, so here are the first three, plus the rung that most readers expect to be the escape. Each row is a complete formal system with a decidable axiom set, and each one is consistent and true of the natural numbers.

Incompleteness sounds like a defect a system might have and might be cured of, in the way a program might have a bug. For arithmetic that reading is wrong, and the exact word for what is wrong with it is essential. A system is essentially incomplete when not only it, but every consistent, effectively axiomatized system that contains it, is incomplete as well. The tower is not a series of unlucky accidents; it is what essential incompleteness looks like from the inside.

The contrast makes the definition concrete, because merely incomplete systems that can be completed are common and unremarkable.

The repair has a mirror image that is far more often described than described correctly. Instead of adding G, add its denial: take TNT + not-G, a system that asserts, in effect, that some number codes a derivation of G. This is not a nonsense system and it is not an inconsistent one. If TNT is consistent, then TNT + not-G is consistent, and the argument is a single step: consistency of TNT is exactly what guarantees G is not derivable in TNT, and a sentence that cannot be derived can have its denial added without contradiction.

Notice which branch needs which assumption, because they are not the same. The denial branch needs only that TNT is consistent. The branch that adds G needs the stronger assumption that TNT's theorems are actually true of the natural numbers — bare consistency does not by itself rule out that TNT derives not-G. If Rosser's sentence from 1936 is used in place of G, plain consistency is enough for both branches at once, which is one reason that variant is the one modern treatments prefer.

So both branches are available, both are consistent, and mathematics has no procedural objection to either. What separates them is not consistency. It is what their models look like.

A consistent system is one that never derives a contradiction. A true system is one whose theorems hold of the natural numbers as ordinarily understood — the standard model, the structure containing zero, one, two, and nothing else. These two properties are frequently treated as the same property, and the second branch of the fork is where the difference becomes impossible to ignore.

G is true in the standard model. So not-G is false in the standard model, and a system with not-G among its axioms cannot have the standard model among its models: the ordinary whole numbers simply fail to satisfy that axiom. Yet TNT + not-G is consistent, and a consistent first-order theory always has some model. Both facts hold at once, and the only way for them to hold together is for every model of TNT + not-G to be something other than the ordinary whole numbers.

Those other structures are the non-standard models of arithmetic. Every model of TNT contains an initial run of elements named by the numerals 0, S0, SS0, and so on; a non-standard model contains, in addition, elements that the system's own ordering places above every one of those numerals. Hofstadter's name for such an element is a supernatural number.

Here is what forces one into existence, written out. Not-G says that some number codes a derivation of G. Because TNT is consistent, no ordinary whole number does, and — this is the step that does the work — TNT itself derives, one theorem at a time, that each particular numeral fails to code such a derivation.

not-G says:   some number c codes a derivation of G

TNT derives:  0 does not code a derivation of G
              S0 does not code a derivation of G
              SS0 does not code a derivation of G
              and so on, one separate theorem for every numeral

A model of TNT + not-G must satisfy the top line and every line beneath it. Its witness c is therefore not 0, not S0, not SS0, and not any numeral at all, while still being a number as far as the model is concerned. That element sits above the entire standard part.

Two clarifications keep this from being over-read. Non-standard models are not a Gödel phenomenon by themselves: Thoralf Skolem showed in 1934 that arithmetic has non-standard models regardless, and even the set of all true arithmetical sentences has them. What adding not-G accomplishes is stronger and stranger — it makes the standard model unavailable, so that a system with no false theorem in the ordinary sense has become a system with no ordinary interpretation at all. And these structures are perfectly well behaved: every countable non-standard model of the Peano axioms has the same order shape, the standard part followed by copies of the integers arranged in the dense order of the rationals. The supernatural witness c still satisfies "codes a derivation of G" inside its own model. Decoded from outside, it does not yield a derivation, because it is not a finite object.

Mathematics had already lived through this fork once, two thousand years before Gödel, and the earlier case is what makes the later one recognisable rather than shocking. Euclid's fifth postulate — that through a point not on a given line there passes exactly one parallel to it — resisted every attempt to derive it from the other four. In the nineteenth century the reason became clear: it cannot be derived, because it is independent of them.

Independence was settled the way independence is always settled, by building models. Nikolai Lobachevsky and János Bolyai developed a geometry in which many parallels pass through the point, and Eugenio Beltrami in 1868, followed by Felix Klein and Henri Poincaré, constructed that geometry inside ordinary Euclidean space. A model built out of Euclidean material cannot be inconsistent unless Euclidean geometry is, so denying the fifth postulate is as safe as keeping it. The parallel to arithmetic is exact at this point: an undecided sentence, two consistent extensions, and models establishing that neither branch collapses.

Now the part of the analogy that does not transfer, which matters more than the part that does. Geometry has no single intended structure that the axioms were always trying to describe. Asking which of the Euclidean and hyperbolic planes is the real one is either a question about physical space, answered by measurement rather than by logic, or no question at all; both are legitimate mathematical objects and neither is a mistake. Arithmetic is not like this. The natural numbers are singled out in advance by counting, and that structure is a fixed target the axioms are trying to capture. So the geometry analogy transfers the logical facts — independence, and the consistency of both branches — and stops before the evaluative one. Both branches of the geometric fork are true of something we care about. Only one branch of the arithmetic fork is true of the numbers.

Two smaller precisions are worth carrying with the analogy, since both are routinely dropped. Denying the fifth postulate while keeping the other four gives hyperbolic geometry; the elliptic geometry of the sphere requires altering a second postulate as well, since on a sphere a line cannot be extended indefinitely without returning. And the sense in which the standard model is singled out has a formal counterpart: the Peano axioms stated in second-order logic, quantifying over all sets of numbers, do pin the natural numbers down uniquely, which is Dedekind's categoricity result. That formulation escapes the tower only by giving up effective axiomatization — its logical consequences cannot be mechanically enumerated — so it buys uniqueness with exactly the coin the incompleteness theorem charges.

Protocol. Select each branch of the arithmetic fork in turn and record two things: whether the branch is consistent, and whether the ordinary whole numbers remain a model. Then place the geometry fork beside it and check that the first answer matches on both sides while the second does not, since the geometric fork has no privileged structure to lose. On the denial branch, find the element the panel marks as supernatural and confirm it is placed above every displayed numeral rather than between two of them.

Limits. The panel asserts that a model exists on each branch rather than constructing one; the construction requires the completeness theorem for arithmetic and a model built inside Euclidean space for geometry. It also shows a single supernatural element where a model contains infinitely many, arranged in blocks. Most importantly, "both branches are consistent" is a claim about derivability only, and the panel deliberately does not label either arithmetic branch true, because truth is settled by the standard model rather than by the fork.

The tower has a historical target, and reading the chapter without it makes the result look like a curiosity instead of the end of a research programme. In the 1920s David Hilbert proposed to secure mathematics by formalizing it completely and then proving, by finitary means — a restricted, concrete, combinatorial style of reasoning that nobody could reasonably doubt — that the resulting formal system can never derive a contradiction. Infinitary mathematics would then be safe to use, because its consistency would rest on a foundation no more questionable than counting. Gödel's second incompleteness theorem states that a consistent, effectively axiomatized system of sufficient strength cannot derive the sentence expressing its own consistency, and finitary reasoning was expected to be formalizable inside such a system. The consistency proof Hilbert wanted therefore cannot exist in the form he wanted it.

What replaced it is more interesting than a defeat. In 1936 Gerhard Gentzen proved the consistency of arithmetic outright. His proof assigns ordinals to derivations and argues by transfinite induction up to ε₀, the limit of ω, ω raised to ω, ω raised to that, and so on upward. The proof is correct, the result is real, and its induction principle is not available inside arithmetic and is not finitary in Hilbert's sense — which is not an embarrassment but the exact measurement Gödel's theorem predicted. A consistency proof must reach beyond the system it certifies, and Gentzen's tells us precisely how far beyond: one ordinal, named.

The chapter's title invites a picture in which the system, confronted with its own limitation, somehow steps outside itself. Nothing of the sort happens, and being firm about this is the difference between understanding the result and repeating a slogan. Set a system grinding: it enumerates derivations one after another, checking each for G. If TNT is consistent, that search runs forever and reports nothing. The system never concludes that G is underivable, because concluding it would require surveying an infinite search that has not finished.

A reasoner standing outside settles the question immediately, and it is worth being exact about what that reasoner uses. They know the coding, so they can read G as the arithmetical claim it is. They assume the system is consistent. From those two things, G's truth follows in one step: consistency means no derivation of G exists, and G says that no derivation of G exists. The jump is performed by a reader with an extra premise, not by a machine that transcended its rules.

The last two steps are the point of the diagram, and they are a theorem rather than a picture. Arithmetic can derive the conditional statement that if it is consistent then its own Gödel sentence holds — the first incompleteness proof, formalized inside the system it is about.

TNT derives:   if TNT is consistent, then G
TNT does not derive:   TNT is consistent

So the outside reasoner's insight is not something machines are shut out of. The machine already has the implication; what it lacks is the premise. Writing the premise down produces a new, larger system, and that system is effectively axiomatized, consistent and strong enough — so it has its own undecidable sentence, and the reasoner who wants to settle that one needs the same trick again, one level up.

Hofstadter names the stances involved earlier in the book. Working strictly inside the rules, shuffling symbols and never asking what they mean, is the Mechanical mode. Standing outside and reasoning about the system — noticing patterns in what it can and cannot derive — is the Intelligent mode. His third, the Un-mode, is the Zen-flavoured refusal to be captured by the framing at all. The chapter's conclusion is a statement about the relationship between the first two: you can always climb out of any particular system by moving to a wider one, and you can never climb out of every system at once, because the climbing itself takes place somewhere.

Protocol. Run the trace and record the step count at which the inside track is still searching while the outside track has already reported an answer. Read the outside track's justification and identify the one premise it uses that the inside track does not have. Then run the trace again with the consistency premise granted to the inside track, and record what the inside track can now settle and what it still cannot — the second of these is the new undecidable sentence, and it should be a different sentence from the first.

Limits. The trace displays a finite prefix of a search that does not terminate, so the never-terminating claim comes from the theorem and not from the display; no length of trace establishes it. The outside observer is drawn as though it obtains the answer for free, which conceals the assumption it depends on — the panel should be read with that assumption named. And the observer's reasoning is not shown being formalized into the larger system, which is the step that keeps the jump from being magical.

The most attractive misreading of this chapter is that people can do something machines cannot, since a person sees the truth of a machine's Gödel sentence while the machine cannot derive it. This is the argument J. R. Lucas advanced in 1961 and Roger Penrose revived in a more elaborate form, and it fails at a step that this chapter has already made visible.

Seeing that G is true requires assuming the system is consistent. Grant a machine that same assumption, as an axiom, and it derives G too — the implication from consistency to G is a theorem of the system itself. So the person's advantage is not an ability to derive something underivable; it is the willingness to assert a premise. To convert that willingness into a genuine advantage, a person would have to be entitled to assert their own consistency, with the same reliability with which they can inspect a formal system's axiom list. Nobody has that entitlement. Human mathematical reasoning is not a surveyable axiom set, its consistency has never been established, and the historical record of published errors argues against granting it for free. The argument needs an unearned premise about ourselves that it never supplies.

Hofstadter himself rejects the Lucas argument, and this is not a case of a popular writer being co-opted by his readers. The honest summary is that the incompleteness theorems are results about formal systems, and every attempt to convert them into a result about minds imports a claim about minds that the theorems do not contain.

The tower and the fork are strong results with narrow content, and nearly every misuse in circulation comes from widening one of them by a step. The table separates the claim from what actually follows.

The study closes here, and what it leaves behind is a small set of tools that apply well beyond this book. You can take an incomplete formal system, add its undecidable sentence, and say exactly why the repair produces a stronger system that is incomplete in the same way — and you can name the condition, effective axiomatization, whose removal would stop the argument. You can take the other branch and describe what you get: a consistent system with no standard model, whose elements include supernatural numbers above every numeral, and you can explain why consistency never promised truth. You can run the Euclid analogy and say where it stops. And you can describe the jump precisely: a reasoner outside, using an assumption of consistency, whose reasoning becomes a larger system with a new sentence of its own.

The chapters after this one take the same shape further rather than repeating it. Self-reference and self-reproduction turn out to be one subject rather than two; Tarski's theorem shows that truth, unlike derivability, cannot even be defined inside the system; and the strange loop stops being a fact about arithmetic and becomes a proposal about minds. Those are the natural continuations, and they are available in the book whenever you want them.

• [ ] Can you say why adding G produces a system that is still effectively axiomatized?
• [ ] Can you state essential incompleteness without using the word "always"?
• [ ] Can you explain why adding an infinite list of Gödel sentences does not escape the tower?
• [ ] Can you say which branch of the fork needs only consistency, and which needs more?
• [ ] Can you define a supernatural number by what the ordering does to it?
• [ ] Can you name the part of the Euclid analogy that does not transfer, and why?
• [ ] Can you say what the outside reasoner supplies that the system lacks?
• [ ] Can you explain why "take all true sentences as axioms" is not a counterexample?

The primary literature for this chapter is unusually approachable, and the corrective literature on misuse is better still.

• Douglas R. Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid, Chapter XV, Basic Books, 1979.
• Gerhard Gentzen, "Die Widerspruchsfreiheit der reinen Zahlentheorie", Mathematische Annalen 112, 1936, pages 493–565.
• David Hilbert, "Über das Unendliche", Mathematische Annalen 95, 1926, pages 161–190, for the programme in the author's own words.
• Alan M. Turing, "Systems of Logic Based on Ordinals", Proceedings of the London Mathematical Society 45, 1939, pages 161–228.
• Solomon Feferman, "Transfinite Recursive Progressions of Axiomatic Theories", Journal of Symbolic Logic 27(3), 1962, pages 259–316.
• Alfred Tarski, Andrzej Mostowski and Raphael M. Robinson, Undecidable Theories, North-Holland, 1953, for essential incompleteness of the weak base system.
• Thoralf Skolem, "Über die Nicht-charakterisierbarkeit der Zahlenreihe mittels endlich oder abzählbar unendlich vieler Aussagen mit ausschliesslich Zahlenvariablen", Fundamenta Mathematicae 23, 1934, pages 150–161.
• Richard Kaye, Models of Peano Arithmetic, Oxford University Press, 1991, for non-standard models in detail.
• Torkel Franzén, Gödel's Theorem: An Incomplete Guide to Its Use and Abuse, A K Peters, 2005.
• Panu Raatikainen, "Gödel's Incompleteness Theorems", Stanford Encyclopedia of Philosophy.

The chapter answers one question — does bolting on the missing sentence fix the system — and the answer has two halves that must be kept apart.

• Adding G yields a new system that is consistent, effectively axiomatized and strong enough, so the construction runs again and produces a new undecidable sentence.
• Essential incompleteness means every consistent, effectively axiomatized extension is incomplete, which is a property rather than a curable defect; merely incomplete systems, such as Euclid's first four postulates, can be completed.
• Adding an infinite but mechanically generated list of Gödel sentences does not escape, because effective axiomatization is about recognisability, not size.
• Adding not-G is also consistent when the base is consistent, and the resulting system has no standard model at all; every model contains supernatural numbers above every numeral.
• Consistency and truth are different properties, and the denial branch is exactly where they come apart.
• The Euclid analogy transfers independence and consistency, and stops before evaluation, because arithmetic has an intended structure and geometry does not.
• Hilbert wanted a finitary consistency proof; the second theorem rules it out, and Gentzen's 1936 proof by transfinite induction up to ε₀ succeeds precisely by not being finitary.
• The system does not jump; a reasoner outside assumes consistency and reads G's truth off, and formalizing that reasoner produces a larger system with its own undecidable sentence.
• The step from this to "minds beat machines" fails, because a machine granted the consistency assumption derives G too, and no one has privileged access to their own consistency.