Matpic
mathematics, in pictures
Logic

A sequence that explodes and still stops

Goodstein's sequence starting at 4 climbs past any number you care to name and reaches zero after about ten to the hundred and twenty million steps. The proof that it stops is a second sequence, running alongside it, that goes down.
19 min read 8 figures What a system cannot saySmall cases lie

Worth reading first: The sentence that says it has no proof.

Here is a rule. Write a number in base 2, with the exponents also written in base 2, and so on all the way down. Replace every 2 by a 3. Subtract one. Then write the result in base 3 the same way, replace every 3 by a 4, subtract one, and keep going.

The Goodstein sequence from 3, with the ordinal beside each termA table of the Goodstein sequence with each term's hereditary representation and the ordinal obtained by replacing the base with omega.basevaluein hereditary baseordinal232 + 1ω + 1333ω4333522261117000G(3) written in hereditary base b, the base bumped to b+1, then one subtractedthe integers reach 0 after 5 steps, and the ordinals fall the whole way
Fig. 1 The sequence starting at 3, in full. Six terms and it is over. The right-hand column is the ordinal obtained by replacing the base with ωω, and it strictly decreases at every step — computed by an ordinal comparison written for the purpose, never inferred from the integers beside it.

Starting at 3 the sequence is 3,3,3,2,1,03, 3, 3, 2, 1, 0. That is unremarkable. Starting at 4 it is not.

The Goodstein sequence from 4, with the ordinal beside each termA table of the Goodstein sequence with each term's hereditary representation and the ordinal obtained by replacing the base with omega.basevaluein hereditary baseordinal242^2ω^ω3263^2·2 + 3·2 + 2ω^2·2 + ω·2 + 24414^2·2 + 4·2 + 1ω^2·2 + ω·2 + 15605^2·2 + 5·2ω^2·2 + ω·26836^2·2 + 6 + 5ω^2·2 + ω + 571097^2·2 + 7 + 4ω^2·2 + ω + 481398^2·2 + 8 + 3ω^2·2 + ω + 391739^2·2 + 9 + 2ω^2·2 + ω + 21021110^2·2 + 10 + 1ω^2·2 + ω + 11125311^2·2 + 11ω^2·2 + ω1229912^2·2 + 11ω^2·2 + 11G(4) written in hereditary base b, the base bumped to b+1, then one subtractedthe integers keep rising, and the ordinals fall at every single step — which is why it has to stop
Fig. 2 The sequence starting at 4, for eleven steps. The integers climb — 4, 26, 41, 60, 83, 109, 139, 173, 211, 253, 299 — and the ordinals fall at every single one. It reaches zero eventually, after a number of steps with more than a hundred million digits.

The sequence from 4 rises for a very long time and then comes down, reaching zero at step 3⋅2402653211−23 \cdot 2^{402653211} - 2. That exponent is not an estimate; the length has a closed form and this is it. Every Goodstein sequence reaches zero, from every starting number, and the proof is short.

What hereditary base notation is

The word hereditary is doing all the work and it is the only piece of notation to learn.

Write 26 in base 3 the ordinary way: 26=2⋅9+2⋅3+226 = 2 \cdot 9 + 2 \cdot 3 + 2, so 26=2⋅32+2⋅3+226 = 2 \cdot 3^2 + 2 \cdot 3 + 2. Now look at the exponents. The 2 in 323^2 is itself a number, and it should be written in base 3 too — here it already is, since 2<32 < 3. Had the exponent been 5, it would become 3+23 + 2, and any exponent inside that would be treated the same way, until nothing larger than the base appears anywhere.

That is hereditary base bb: the base and every exponent, and every exponent of an exponent, written using nothing above bb.

The bumping step then means something precise. Replace every occurrence of bb — in the base position, in the exponents, everywhere — by b+1b+1. And then subtract one.

Subtracting one is the only thing that ever makes the number smaller, and it is a puny operation compared with the bump. 22=42^2 = 4 bumps to 33=273^3 = 27, and subtracting one leaves 26. The next bump takes 2⋅32+2⋅3+2=262 \cdot 3^2 + 2 \cdot 3 + 2 = 26 to 2⋅42+2⋅4+2=422 \cdot 4^2 + 2 \cdot 4 + 2 = 42, minus one is 41. The bump multiplies; the subtraction chips.

The trick

Replace the base by ωω.

That is the whole proof. Take the hereditary base-bb representation and write ωω everywhere bb appears. 222^2 becomes ωωω^ω. 2⋅32+2⋅3+22 \cdot 3^2 + 2 \cdot 3 + 2 becomes ω2⋅2+ω⋅2+2ω^2 \cdot 2 + ω \cdot 2 + 2. What comes out is an ordinal, and the sequence of ordinals is what the third column of the figures shows.

Now watch what the two operations do to it.

The bump does nothing. Bumping replaces bb by b+1b+1 everywhere, and the ordinal was obtained by replacing the base by ωω everywhere — so the ordinal of the bumped number is the same ordinal. The bump, which is the operation that makes the integer explode, is invisible at the ordinal level.

Subtracting one strictly decreases it. Subtracting one from a number changes its representation in a way that always lowers the corresponding ordinal — the leading term drops, or a coefficient drops, or a tail of smaller terms appears in place of a larger one.

So the ordinals strictly decrease, at every step, while the integers rise.

The Goodstein sequence from 2, with the ordinal beside each termA table of the Goodstein sequence with each term's hereditary representation and the ordinal obtained by replacing the base with omega.basevaluein hereditary baseordinal222ω322241115000G(2) written in hereditary base b, the base bumped to b+1, then one subtractedthe integers reach 0 after 3 steps, and the ordinals fall the whole way
Fig. 3 The smallest interesting case: 22 in hereditary base 2 is just 22, so the ordinal is ωω, and three steps later the sequence is over. Every Goodstein sequence ends this way; only the number of steps differs.

Why decreasing is enough

Ordinals are well-ordered: every non-empty collection of them has a least member, and equivalently, there is no infinite strictly decreasing sequence.

That property is what the whole argument rests on and it is worth seeing why it is not obvious. The whole numbers are well-ordered, and “a decreasing sequence of whole numbers must stop” is a familiar fact used everywhere — Euclid’s algorithm halts for exactly this reason, and so does every tableau. The ordinals extend the whole numbers past infinity and keep the property, which is precisely what they were invented for.

Order types drawn on the line: ω, ω+1, ω·2, ω²Number lines with tick marks accumulating at limit points, one line per order type.ωω+1ω·2ω²each mark is one step; a taller mark is a place with no step just before it4 order types, drawn by squeezing each run of steps into a finite width
Fig. 4 Four order types drawn on the line. ωω is the whole numbers accumulating at a point; ω+1ω+1 has one more step after all of them; ω⋅2ω \cdot 2 is two such runs; ω2ω^2 is a run of runs. In each the marks strictly increase and each taller mark is a place with no step just before it — both facts checked on the drawn positions.

The picture makes the crucial feature visible. Look at ω+1ω+1: there is a point after every point of ωω, and any decreasing sequence starting there must drop below it in one step, into ωω, and from there it is an ordinary decreasing sequence of whole numbers. There is nowhere to hide an infinite descent, at any of these order types, and the same holds all the way up to ε0ε_0, which is where the Goodstein ordinals live.

So the argument finishes: the ordinals strictly decrease, a strictly decreasing sequence of ordinals is finite, so the sequence of steps is finite, so the integers reach zero.

What the figures assert

The figures compute the ordinal sequence and the integer sequence by different routes and compare them.

The integers come from the hereditary representation, evaluated at the bumped base, minus one, in exact arithmetic — the numbers get large enough that ordinary floating point is useless, so they are computed as big integers. The ordinals come from the same representation with the base replaced by ωω, and are compared using an ordinal comparison written for the purpose: leading exponents first, recursively, then coefficients.

The assertion is that each ordinal is strictly less than the one before it, checked at every drawn step. That comparison never consults the integer beside it, which is the point — a comparison inferred from the integers would be circular, since the integers are going up.

The Goodstein sequence from 5, with the ordinal beside each termA table of the Goodstein sequence with each term's hereditary representation and the ordinal obtained by replacing the base with omega.basevaluein hereditary baseordinal252^2 + 1ω^ω + 13273^3ω^ω42554^3·3 + 4^2·3 + 4·3 + 3ω^3·3 + ω^2·3 + ω·3 + 354675^3·3 + 5^2·3 + 5·3 + 2ω^3·3 + ω^2·3 + ω·3 + 267756^3·3 + 6^2·3 + 6·3 + 1ω^3·3 + ω^2·3 + ω·3 + 1711977^3·3 + 7^2·3 + 7·3ω^3·3 + ω^2·3 + ω·3817518^3·3 + 8^2·3 + 8·2 + 7ω^3·3 + ω^2·3 + ω·2 + 7924549^3·3 + 9^2·3 + 9·2 + 6ω^3·3 + ω^2·3 + ω·2 + 6G(5) written in hereditary base b, the base bumped to b+1, then one subtractedthe integers keep rising, and the ordinals fall at every single step — which is why it has to stop
Fig. 5 Starting at 5. The first term’s hereditary form is 22+12^2 + 1, so the first ordinal is ωω+1ω^ω + 1 — one step above the ordinal that starts the sequence from 4, and correspondingly the sequence takes very much longer.

The ordinals, built rather than assumed

The proof leans on ordinals and it is worth saying what they are, because a reader who takes them on faith has taken the whole argument on faith.

An ordinal is an order type: what is left of a well-ordered set once everything except the order is forgotten. The whole numbers in their usual order have order type ωω. Put one extra element after all of them and the type is ω+1ω + 1 — a different type, because in ωω every element has finitely many below it and in ω+1ω+1 the last one does not. Two copies of ωω end to end is ω⋅2ω \cdot 2; ωω copies of ωω is ω2ω^2; and continuing gives ω3ω^3, ωωω^ω, and beyond.

Order types drawn on the line: ω, ω+1Number lines with tick marks accumulating at limit points, one line per order type.ωω+1each mark is one step; a taller mark is a place with no step just before it2 order types, drawn by squeezing each run of steps into a finite width
Fig. 6 The first two, drawn larger. In ωω the marks accumulate at a place with no mark; in ω+1ω+1 there is a further mark after that place. The figure checks that each limit mark is where the marks before it pile up, and that nothing sits in the gap between the pile-up and the limit.

Two things are worth noticing about the drawing, because they are where the picture is a convention rather than a fact.

The compression is a drawing decision. Each run of ωω steps is squeezed into a finite width so it can be shown, and nothing in the mathematics is compressed — there is no metric on an order type, and the tick positions are not measurements of anything. What is real is the order, and the assertions are about order: the marks strictly increase, and each limit mark has infinitely many marks below it and nothing immediately before it.

ε0ε_0 is not drawable at all. The Goodstein ordinals live below ε0ε_0, the first ordinal satisfying ωα=αω^α = α — the limit of ωω, ωωω^ω, ωωωω^{ω^ω} and so on. Every ordinal below it has a finite Cantor normal form and can be written down; the drawing runs out several floors below that, and the essay says so rather than producing something suggestive.

Where the interest is

Goodstein proved the theorem in 1944 and it would be a curiosity if that were all. What makes it matter is a result of Kirby and Paris from 1982.

Goodstein’s theorem is not provable in Peano arithmetic.

It is a statement entirely about whole numbers: for every nn, the sequence starting at nn reaches zero. Every instance of it is a finite computation. And the usual axioms for arithmetic cannot prove the general statement.

That is what Gödel’s theorem promised and did not deliver in a natural form. Gödel’s sentence is constructed to be unprovable, and a reader can fairly say it is a contrivance. Goodstein’s theorem is about sequences of whole numbers, was written down for its own sake, and nobody arranging an unprovable statement would have produced it.

The reason it escapes is visible in the proof. The argument uses induction along the ordinals up to ε0ε_0, and Peano arithmetic can carry out induction along the ordinals below ε0ε_0 but not up to ε0ε_0 itself. That exact boundary is Gentzen’s, from his 1936 consistency proof, and Goodstein’s theorem sits precisely on the wrong side of it.

So the theorem is true, its proof is three paragraphs, and the proof cannot be carried out in arithmetic. The extra ingredient is not a new fact about numbers; it is the well-ordering of a particular infinite order type, and that is a statement about ordinals rather than about integers.

The hydra, which is the same theorem in a costume

There is a second version of this result that is worth knowing because it removes the arithmetic entirely and leaves the structure.

Hercules fights a hydra, which is a tree. At each step he chops one head — a leaf — and the hydra responds by growing nn copies of the subtree just above where the cut was made, where nn is the step number. The copies grow fast; by step ten the hydra is enormously larger than when the fight started.

Hercules always wins, no matter how he chooses which head to chop, and the proof is the same proof: assign an ordinal to the tree, show that chopping strictly decreases it, and note that the growth does not increase it. The result, also due to Kirby and Paris, is likewise not provable in arithmetic.

What the hydra adds is the observation that the strategy does not matter. Any sequence of choices terminates, which is a much stronger statement than some sequence terminates and is the reason ordinals are the right tool rather than a convenient one: there is no clever play to find, because there is no bad play to avoid.

Both versions share the feature that makes them good examples. The process gets dramatically bigger at every step, by any measure a person would reach for, and terminates anyway — so the intuition that growing means not stopping has to be given up, and what replaces it is the observation that growth and termination are measured by different things.

Why the small cases lie

The sequence from 3 terminates in six steps. The sequence from 4 takes a number of steps whose decimal expansion has over a hundred million digits. The sequence from 5 is very much worse again, and 19 is beyond any description worth attempting.

The Goodstein sequence from 2, with the ordinal beside each termA table of the Goodstein sequence with each term's hereditary representation and the ordinal obtained by replacing the base with omega.basevaluein hereditary baseordinal222ω322241115000G(2) written in hereditary base b, the base bumped to b+1, then one subtractedthe integers reach 0 after 3 steps, and the ordinals fall the whole way
Fig. 7 Starting at 2: three steps and it is done. The smallest cases are so short that nothing about the behaviour is visible in them, which is why this is a good example of a claim that cannot be understood by checking examples.

That gap between the first two interesting cases is worth dwelling on. Anyone experimenting would try 1, 2, 3 — all trivial — and then 4, and would never see it terminate. The evidence available to experiment is a handful of instant terminations followed by one apparently unbounded climb, and the correct conclusion from that evidence is “probably diverges”.

This is the standing warning in the collection’s small cases lie thread, in an unusually sharp form: the cases within reach are not merely a small sample, they are actively misleading, and no amount of computing power changes that. Running the sequence from 4 further does not help, because there is no point in the run where anything begins to look like turning round.

Order types drawn on the line: ω·2, ω²Number lines with tick marks accumulating at limit points, one line per order type.ω·2ω²each mark is one step; a taller mark is a place with no step just before it2 order types, drawn by squeezing each run of steps into a finite width
Fig. 8 Two order types at a larger scale. ω⋅2ω \cdot 2 has one place where the marks pile up and then start again; ω2ω^2 has infinitely many such places, each with its own pile-up before it, and the figure checks that nothing sits in any of the gaps.

Two things the theorem does not say

It does not say the sequence is unpredictable. Every term is computed by a completely explicit rule, and the length of the whole sequence has a closed form. The sequence from 4 takes exactly 3⋅2402653211−23 \cdot 2^{402653211} - 2 steps, and that number was not measured — it was derived. Nothing here is chaotic; the difficulty is entirely one of scale.

It does not say arithmetic is wrong about it. Peano arithmetic proves every instance of Goodstein’s theorem — for any particular nn, it can prove that the sequence from nn terminates, because that is a finite computation and arithmetic can verify finite computations. What it cannot prove is the sentence “for all nn”. The gap is between infinitely many provable statements and the single statement that summarises them, and it is exactly the gap incompleteness predicts.

That second point is the one worth carrying, because it is what an independence result usually looks like from close up. Nothing is undecided about any concrete case; what is missing is the general theorem, and the general theorem is missing because proving it needs an induction the system cannot perform.

What the ordinal is really doing

It is worth extracting the technique, because it is the general method for proving that something terminates.

Find a quantity that decreases at every step, in an order with no infinite descent. Then the process cannot go on forever, whatever else it does. The quantity does not have to be the size of anything, or bounded, or computable in advance; it only has to decrease.

For most terminating processes the quantity is a whole number and the argument is unremarkable — the length of a formula, the size of a remainder, the number of unmarked vertices. Goodstein’s sequence is the standard example of a process where no whole-number quantity will do, because the terms rise without bound and any function of the term does too, and yet an ordinal quantity is available and settles it.

That is the reason ordinals earn their place outside set theory. They are the general-purpose measure for termination, applicable exactly when a whole number is not enough, and this theorem is the cleanest case of the gap between the two.

There is a last observation about the shape of the argument that this collection should not let pass. The integer sequence and the ordinal sequence are the same object written twice — one with bb where the other has ωω — and they behave in opposite directions. Nothing was added to the problem; the base was replaced by a symbol, and a question with no visible answer acquired a one-line one. That is not a proof technique so much as a change of notation that made the proof unnecessary, which is the best thing a change of notation can do, and it is the same move that turns a hard counting problem into an easy one by counting the same collection two ways.

It is worth ending on how ordinary the rule is. Nothing about write it in base bb, bump the base, subtract one looks like it belongs to foundations. It is the kind of thing that could be set as a puzzle to a child, and every individual step is arithmetic anybody can do. The sequence from 4 could in principle be computed by hand for a hundred steps in an afternoon, and nothing in those hundred steps would suggest anything at all.

And yet the general statement about it sits outside the axioms of arithmetic, and the shortest correct proof passes through the well-ordering of an infinite order type. That combination — a completely elementary question whose answer requires leaving the elementary — is rare, and it is why this theorem is the standard example rather than one example among many. It is the clearest available evidence that the boundary Gödel drew is not a boundary between ordinary mathematics and exotic mathematics. It runs straight through the middle of the ordinary kind.

Where this goes next

φ10110101000φ21101010000φ30011111000φ41010100000φ50001001000φ60111110000φ71110011001φ8010100000110011001neweach row is a sentence, and whether it says yes to each numbered question; the markedsquares are the diagonalthe row underneath is the sentence that answers each question the opposite way to theone asked about it — so the answers cannot all be given by a sentence on the list The sentence that says it has no proof Number every sentence and every proof, and a formal system can talk about itself. Then the diagonal is available one more time, and what it builds is a sentence that is true exactly when it is unprovable. every node has at most 3 children and the tree reaches level 416 nodes on the bottom row; the marked walk takes a surviving child at every step An infinite tree has an infinite path A tree that goes on forever, in which every node has only finitely many children, must contain a single branch that goes on forever. The proof is a rule for walking, and the rule is the whole of why finite information can decide an infinite question. 9232127 reaches 1 in 111 steps, after climbing to 9232the vertical scale is logarithmic, because the climb is the interesting part and it is steep The question nobody can answer Halve it if it is even, triple it and add one if it is odd. Every number anyone has tried comes down to one. Nobody can prove they all do, and the reason is not that the problem is hard to state.

What links here

Computed from the collection, not written here: the essays that point at this one.

Named objects

A dashed tag is an object no other essay names yet.

Goodstein sequenceHereditary baseIndependenceOrder typeOrdinalTerminationTransfinite inductionWell ordering