An ordinal as a growth rate

The first rung of this ladder said that the Goodstein sequence from four reaches zero “after a number of steps with more than a hundred million digits”, which is a way of saying that the number is too large to describe. It is not. It can be named exactly, and naming it requires turning an ordinal into a growth rate.

The construction is three lines. Start with the function that adds one. At a successor ordinal, take the previous function and apply it to its own argument that many times. At a limit ordinal, use the fundamental sequence: evaluate at the argument’s own place in the sequence.

$$F_0(n) = n + 1, \qquad F_{α+1}(n) = \underbrace{F_α(F_α(\cdots F_α}_{n \text{ times}}(n)\cdots)), \qquad F_λ(n) = F_{λ[n]}(n).$$

The first three, which have closed forms #

$F_1$ applies $F_0$ to $n$ exactly $n$ times, adding one each time, so $F_1(n) = 2n$.

$F_2$ applies $F_1$ to $n$ exactly $n$ times, doubling each time, so $F_2(n) = n \cdot 2^n$.

$F_3$ applies $F_2$ that many times, and there is no closed form worth writing: it is a tower of exponentials whose height is about $n$. The figures compute the first three rows exactly and assert the two closed forms above at every value they compute — which is a check on the recursion rather than an illustration of it, because a recursion and a formula agreeing is the kind of thing that fails silently when the recursion is written down slightly wrong.

What happens at a limit #

$F_ω$ is where the ordinals start doing work rather than counting. There is no “previous” function to iterate, so the definition reaches for the fundamental sequence of $ω$, which is $1, 2, 3, \dots$, and sets $F_ω(n) = F_n(n)$.

That is a diagonal, in the same sense as the argument that no list holds every row: the new function is defined by walking down the list of old ones, taking the $n$-th at $n$. And as there, the diagonal escapes: $F_ω$ eventually exceeds every $F_k$, because past $n = k$ it is being computed by an $F$ with a larger index.

The choice of fundamental sequence therefore matters, and this is the honest wrinkle in an otherwise clean construction. Different sequences with the same supremum give different functions — not wildly different, but different — so $F_α$ is well defined only once a system of fundamental sequences has been fixed. The standard one is the one the figures use, and its terms are what the normal form supplies. This is the price of using ordinals as indices: an ordinal is an order type and has no canonical sequence attached to it, so the notation does the work rather than the ordinal.

Ackermann, and why the hierarchy is familiar #

$F_ω$ is essentially the Ackermann function, the standard example of a function that is computable but not primitive recursive. The correspondence is exact enough to be worth stating: each $F_k$ for finite $k$ is primitive recursive, every primitive recursive function is eventually dominated by some $F_k$, and $F_ω$ outgrows the lot.

So the hierarchy provides, at its very first limit, the classical separation between “built from loops of bounded depth” and “needs recursion that is not”. The ordinal index is doing the same job as the nesting depth in that older account, and it keeps working past the point where nesting depth runs out of ways to be described.

Iterating, and what iteration buys #

Each step up the hierarchy does one thing: it turns a function into the operation of applying that function repeatedly. That is a small-looking move with an enormous effect, and it is worth watching it happen at the bottom, where everything is visible.

Adding one, iterated, is doubling — the increment is applied as many times as the number being worked on, so the number is added to itself. Doubling, iterated, is multiplication by a power of two, because each application multiplies by two and there are $n$ of them. Multiplying by $2^n$, iterated, produces a tower of exponentials, because each application puts the previous result into an exponent. So the operations produced are, in order: addition, multiplication, exponentiation, towers — the same ladder that repeated operations climb in the ordinary account of arithmetic, arrived at from a single rule rather than defined one at a time.

The ordinal index is therefore counting how many times the idea of iteration has been applied, and the limit case is what allows that count to pass into the infinite. Every essay in this collection about a process that runs away — a map whose orbits separate, a sequence that explodes — is looking at growth several levels below where this hierarchy starts to be interesting, which is a useful calibration: exponential growth is $F_2$, and $F_2$ is the last row a page can print.

Climbing to epsilon #

Past $ω$ the construction continues with no new ideas: $F_{ω+1}$ iterates $F_ω$, $F_{ω \cdot 2}$ diagonalises over $F_{ω + k}$, $F_{ω^2}$ over that, and so on up through every ordinal the normal form can name.

At $ε_0$ the construction gives $F_{ε_0}$, and this function is the point of the whole ladder. It is perfectly well defined, perfectly computable — an algorithm evaluates it, given enough time — and Peano arithmetic cannot prove that it is total.

The theorem behind that, due to Kreisel and refined by many since, is the exact statement of what arithmetic can prove:

A function is provably total in Peano arithmetic exactly when it is eventually dominated by $F_α$ for some $α < ε_0$.

So the ordinals below $ε_0$ are a complete measure of the growth arithmetic can certify, and $F_{ε_0}$ sits one step outside it.

The word “eventually” in that statement is load-bearing and is easy to read past. Domination is a claim about all large enough arguments, not about all arguments: $F_ω$ is smaller than $F_3$ at $n = 3$, and larger from some point on. A hierarchy indexed this way is therefore not a ranking of functions by their values anywhere in particular; it is a ranking by their behaviour at infinity, and every finite table of it is drawn from the region where the ranking has not taken effect.

That also explains why the theorem can be an exact characterisation rather than a rule of thumb. If a function is provably total in arithmetic, then a proof of its totality can be mined for an ordinal below $ε_0$ that bounds its growth — the ordinal is extracted from the proof rather than guessed from the function — and conversely every such bound gives a proof. The correspondence is between proofs and ordinals, and the growth rate is what both of them are measuring. Not because it is uncomputable — that is a different obstruction — but because certifying that it always returns requires induction along an order type arithmetic cannot carry.

The number of steps, named exactly #

Now the Goodstein sequence can be stated properly.

The length of the sequence starting at $n$ is given by the Hardy hierarchy, a cousin of the one above with $H_0(n) = n$, $H_{α+1}(n) = H_α(n+1)$ and the same limit rule. The two hierarchies are related by $H_{ω^α} = F_α$, so the Hardy version measures the same growth with a different indexing.

The Goodstein sequence from $n$ terminates in $H_{ε_0}$ of about $n$ steps. For $n = 4$ that is exactly $3 \cdot 2^{402653211} - 2$ — a number with over a hundred million digits, and an exact expression rather than an estimate. For $n = 5$ and beyond the expression is no longer worth writing, but it exists, and it is a closed form in the same sense.

That is why the independence result feels different from a sentence built to be unprovable. Goodstein’s theorem is a statement about a completely explicit process; what makes it unprovable in arithmetic is that its termination rate is $F_{ε_0}$, and certifying that rate is beyond what induction inside arithmetic reaches. The unprovability is a measurement, not a contrivance.

Two ways a function can fail to be provably total #

It is worth separating the obstruction here from the other one, because both produce a function a system cannot certify and they are not the same failure.

The first is uncomputability. Some functions have no algorithm at all, or have one whose termination is undecidable — the busy beaver function is the standard example, and the reason nothing proves it total is that nothing computes it. That obstruction is about what an algorithm can do.

The second is the one this essay is about, and it is stranger. $F_{ε_0}$ has an algorithm, the algorithm is short, and it terminates on every input. Nothing is unknown about it. What arithmetic lacks is not knowledge of the function but the induction needed to prove that the algorithm returns, and the exact amount of induction it lacks is measured by an ordinal.

The two obstructions can be told apart by what happens when the system is strengthened. Adding induction up to $ε_0$ makes $F_{ε_0}$ provably total immediately, and the new system then has its own ordinal and its own first non-provable rate, one level up. Adding anything at all leaves the busy beaver exactly where it was. Growth is a moving boundary; computability is not.

Past epsilon, briefly #

Nothing stops at $ε_0$ except Peano arithmetic. Stronger systems have larger proof-theoretic ordinals, and the hierarchy climbs alongside them.

The best-known landmark past $ε_0$ in this collection’s neighbourhood is the tree theorem of Kruskal and the function TREE, whose growth is indexed by an ordinal far above $ε_0$ and whose values are beyond every description by towers. The Kirby–Paris hydra, which the first rung of this ladder describes, sits at $ε_0$ alongside Goodstein; the Buchholz hydra goes much further. In every case the pattern is the same: a combinatorial process, an ordinal that measures it, and a system that cannot prove termination because it cannot carry induction that far.

The pattern is worth stating once as a general principle, because it makes independence look ordinary rather than mysterious. A termination proof is an ordinal. How large an ordinal a system can handle is a fixed property of that system; a process whose ordinal exceeds it terminates anyway, and the system cannot say so.

Where the small cases lie, again #

The first two columns of every table above are almost useless as evidence, and it is worth saying why, because the same trap is the reason the Goodstein sequence looks divergent to anybody experimenting.

At $n = 1$, every row of the hierarchy gives $2$. At $n = 2$ the rows give $3, 4, 8, 2048$ and then stop being computable. So the first column says nothing whatever about the differences between the rates, the second column says a little, and the third is already past the edge. A reader with a table of the first two columns would have no way to tell $F_3$ from $F_{ε_0}$, and no amount of extra computing power would change that: the columns that separate the rates are indexed by numbers that cannot be reached.

That is the same shape as the first rung’s warning about experimenting on Goodstein sequences, and it is the standing hazard in this corner of the subject. The evidence available to computation is drawn from a region where the phenomenon has not started, and the phenomenon is defined by what happens outside that region — so extrapolation is not merely unreliable here, it is systematically wrong in a known direction. Every quantity in this essay is larger than any computation, and every one of them is exactly specified.

What the pictures cannot show #

The tables here compute five rows and four columns, and eight of those twenty cells say “beyond”. That is not a defect in the drawing; it is the subject. A hierarchy whose third row is already past evaluation cannot be exhibited, and a figure that showed plausible numbers in every cell would be showing something other than the fast-growing hierarchy.

What the figures do establish is the machinery. The closed forms for $F_1$ and $F_2$ are asserted against the recursion at every value computed, so the definition being drawn is checked to be the definition intended. The fundamental sequences are checked to increase and to stay below their limits, which are the properties the limit case of the recursion needs. And the rows are checked to increase along their length and, where both are computable, to dominate the row above.

The one thing no figure can do is exhibit the domination theorem, which says $F_α$ eventually exceeds $F_β$ for every $β < α$. “Eventually” is past the computable range in every case a picture could contain — the crossover between $F_ω$ and $F_5$ happens at an argument where both are astronomical — so the table can show the first few columns, where the smaller-indexed function is sometimes larger, and the theorem lives entirely in the region no drawing reaches. That is stated in the essay rather than implied by the picture, which is the only honest arrangement.

What this anchor has come to #

Five rungs, and the ordinals have been four different things: a measuring stick for a sequence of integers, an arithmetic of arrangements, a notation with a ceiling, a taxonomy of how limits are approached, and a scale of growth rates. The last is the one that closes the circle, because it turns the first rung’s vague “more than a hundred million digits” into an expression.

What is left undone, and named rather than written: the ordinal analysis of systems past arithmetic, where the notations become the subject; the Veblen hierarchy and $Γ_0$; and the combinatorial statements — Kruskal’s theorem, the graph minor theorem — whose ordinals are far above $ε_0$ and whose independence results are correspondingly stronger. Each is a subject rather than a rung, which is where a ladder should stop.