Every ordinal in base omega

The arithmetic of the previous rung reduced every expression to something of the shape

$$ω^{β_1} \cdot c_1 + ω^{β_2} \cdot c_2 + \dots + ω^{β_k} \cdot c_k, \qquad β_1 > β_2 > \dots > β_k,$$

with each $c_i$ a positive whole number, and used that reduction as though it were obviously available. It is a theorem, it is due to Cantor, and it is what makes ordinals below a certain height into objects a machine can hold.

The statement, and the division behind it #

Every ordinal $α > 0$ has exactly one representation in the displayed form. Existence and uniqueness are both proved by the same device, and it is division with remainder wearing an unfamiliar hat.

For existence: among the ordinals $β$ with $ω^β \le α$ there is a largest, because the exponents cannot increase forever and the ordinals are well-ordered. Call it $β_1$. Then there is a largest whole number $c_1$ with $ω^{β_1} \cdot c_1 \le α$ — largest because $ω^{β_1} \cdot ω$ is $ω^{β_1 + 1}$, which exceeds $α$ by the choice of $β_1$. Subtract on the left, which is the one side subtraction works on, and repeat on the remainder. Each remainder is strictly below $ω^{β_1}$, so the exponents strictly decrease, and a strictly decreasing sequence of ordinals must stop. It stops after finitely many terms.

The finiteness deserves a second look, because it is the property that makes the notation useful and it is not obvious. There is no bound on how many terms an ordinal’s normal form has — the ordinals with $k$ terms exist for every $k$ — and yet no ordinal has infinitely many. The reason is the descent: the exponents form a strictly decreasing sequence of ordinals, and there is no such sequence of infinite length. So a normal form is always finite, always for the same reason, and the length is unbounded without ever being infinite. That combination is exactly what a well-ordering supplies and an ordinary ordering does not; the negative rationals below zero, decreasing, go on as long as anybody likes.

For uniqueness: two such expressions for the same ordinal must have the same leading exponent, since $ω^{β} \cdot c$ with $c$ finite is smaller than $ω^{β+1}$ — so a larger leading exponent anywhere makes the whole expression larger, whatever follows it. Then the leading coefficients must agree, and induction on the number of terms finishes it.

Both halves lean on the same fact: an infinite descending sequence of ordinals is impossible. That is not an extra hypothesis, it is the definition of a well-ordering, and it is the same engine that makes descent arguments work on the whole numbers.

Why a normal form is worth having #

A normal form is not merely a tidy way to write something; it is a decision procedure for equality. Two ordinals below the ceiling are equal exactly when their normal forms are identical lists, and larger exactly when the first place they differ says so — leading exponents first, then leading coefficients, then the rest.

That is why every ordinal figure in this collection can assert what it asserts. The Goodstein sequence’s whole content is that a certain sequence of ordinals decreases while the integers beside it explode, and a comparison inferred from the integers would be circular. With a normal form the comparison is a recursive walk over two nested lists, and it knows nothing about the numbers it is standing beside.

The analogy worth carrying is unique factorisation. The whole numbers have a normal form — a product of primes in increasing order — and it converts questions about equality and divisibility into questions about lists of exponents. Cantor normal form does the same job with $ω$ in place of the primes and addition in place of multiplication, and the payoff is the same: things that were statements about objects become statements about notation, and notation can be manipulated.

The same notation with a number in it #

The hereditary base notation that the Goodstein sequence runs on is Cantor normal form with a number written where $ω$ stands. Writing $n$ in hereditary base $b$ means writing it in base $b$, then writing its exponents in base $b$, and their exponents too, until every number visible is smaller than $b$.

So the map from numbers to ordinals — write $n$ hereditarily in base $b$, then replace every $b$ with $ω$ — is exactly “read this notation as a normal form”. It is strictly increasing, which the figures assert over every number they draw by comparing the resulting ordinals rather than the integers they came from.

Why the bump changes nothing #

That last sentence is the trick, and it is worth stating carefully because it looks like sleight of hand.

The Goodstein step is: write $n$ hereditarily in base $b$, replace every $b$ by $b+1$, subtract one. Replacing the base changes the number — from $4$, which is $2^2$, to $27$, which is $3^3$ — but the ordinal read off the notation is $ω^ω$ before and after, because the ordinal only sees the shape. Then one is subtracted, and subtracting one strictly decreases the ordinal.

So the sequence of ordinals is strictly decreasing, and a strictly decreasing sequence of ordinals cannot be infinite. The integers may do what they like — and they climb for an unimaginably long time — but they are running under a measure that only falls.

The role of the normal form here is precise: without uniqueness the phrase “the ordinal read off the notation” would not define anything, because a number has many base-$b$ expressions if the digits are not required to be below $b$, and different ones would give different ordinals.

Doing the arithmetic in the notation #

Once the normal form exists, the operations of the previous rung become string manipulations, and writing them down is the best way to see where the absorption lives.

To add $α + β$: look at the leading exponent of $β$, throw away every term of $α$ whose exponent is smaller than it, add the coefficients if the leading exponents match, and write the rest of $β$ after. The discarding step is the whole of absorption — it is why $1 + ω$ loses its one — and it is a single line of code rather than an argument about relabelling.

To multiply $α \cdot β$: for each term of $β$ with an infinite exponent, the answer gets a term whose exponent is the leading exponent of $α$ added to that exponent; for a finite term of $β$, the leading coefficient of $α$ is multiplied by it and the rest of $α$ is written after. Non-commutativity is visible in the asymmetry of that description: the leading exponent of $α$ appears on the left of a sum of exponents, and sums of exponents do not commute either.

Both rules are a page of code, both were written for the figures on this ladder, and both are checked against a second, hand-written arithmetic for the ordinals below $ω^2$ over several hundred cases — because a normal form’s whole value is that it makes a claim about ordinals into a claim about lists, and a bug in the list code is then indistinguishable from a false claim about ordinals.

A notation is not an ordinal #

There is a distinction under all of this that is easy to lose and worth making once.

An ordinal is an order type. A notation is a finite object — a tree, a string — together with a rule for reading it as an ordinal and a rule for comparing two of them. The comparison must agree with the order on the ordinals they denote, and the collection of notations, ordered by that comparison, must be a well-ordering that a machine can decide.

Cantor normal form gives such a system for everything below $ε_0$, and the two rules are the ones above. What it does not give is a notation for $ε_0$ itself, and this is where the distinction bites: $ε_0$ is a perfectly ordinary countable ordinal, and the system has run out, not the ordinals. Adding a symbol for $ε_0$ and rules for it produces a larger system with a larger ceiling, and that process never terminates — every notation system has a first ordinal it cannot name, which is the ordinal-analysis version of a system unable to settle a question about itself.

The practical consequence is the one the figures depend on. When a drawing here says two ordinals are equal, it means two notations reduce to the same list. That is a statement about ordinals only because the reading rule is faithful — which is a theorem, and one that has to be proved for each new system rather than assumed from the notation looking sensible.

Where the notation runs out #

The exponents in a normal form are themselves ordinals, so they are themselves normal forms, and so on. Every such expression is a finite tree, and every finite tree is an ordinal — but not every ordinal is a finite tree.

Consider the sequence $ω$, $ω^ω$, $ω^{ω^ω}$, and so on: each term is $ω$ raised to the one before. Every term is a normal form. Their supremum is not, because any normal form for it would have a leading exponent below it, and $ω$ raised to anything below the supremum is still below the supremum. So the supremum $ε_0$ satisfies

$$ω^{ε_0} = ε_0,$$

and it is the smallest ordinal that does — the first fixed point of exponentiation, and the first ordinal that cannot be written in terms of smaller ones using $+$, $\cdot$ and $ω^{(-)}$.

Small, countable, and out of reach anyway #

Two facts about $ε_0$ are worth putting side by side, because together they are the surprise.

It is countable. Every ordinal below it is a finite tree over a finite alphabet, there are countably many such trees, and $ε_0$ is their supremum — so $ε_0$ is a countable ordinal, in the same sense that the rationals are countable: there is a listing. Nothing about it is large in the way that an uncountable set is large.

It is nevertheless beyond Peano arithmetic. Induction along the ordinals below $ε_0$ can be carried out inside arithmetic for each notation separately, and induction up to $ε_0$ cannot — that is Gentzen’s boundary, from his 1936 consistency proof, and it is exactly where Goodstein’s theorem sits.

So the ordinal that measures the strength of arithmetic is a countable ordinal with a completely explicit notation system, every element of which a machine can compare, and the whole of it can be described in a paragraph. Being out of reach of a formal system has nothing to do with being large or being vague. It has to do with what the system can carry out induction along, and that is a much finer measurement than size.

Past the ceiling #

Ordinals do not stop at $ε_0$, and neither do notation systems; they simply become harder to write.

Above $ε_0$ come $ε_1$, $ε_2$ and the rest of the fixed points, then fixed points of the enumeration of fixed points, and the whole tower is organised by the Veblen functions. That construction has its own ceiling, $Γ_0$, the first ordinal closed under all of it — and $Γ_0$ measures a system stronger than arithmetic in the same way that $ε_0$ measures arithmetic.

The programme of assigning such an ordinal to a formal system is ordinal analysis, and its aim is exactly the measurement above: not whether a system is consistent, which it cannot settle about itself, but how much well-ordering has to be assumed to prove that it is. The answers are notations, and the notations get baroque quickly. Every one of them still has the two properties this rung is about — a canonical form for each ordinal, and a mechanical comparison of two of them — because without those there is nothing to compute with.

What the pictures cannot show #

The tables draw a finite initial segment. Eighteen numbers, or thirty, and the general theorem is about every ordinal below $ε_0$ — of which there are uncountably many notations’ worth of, in the sense that no listing appears in any figure. What the drawings do is exhibit the shape of the notation and check the properties that make it a normal form on every entry they contain: the exponents descend, the coefficients are positive, the ordinals increase, and each hereditary form reads back as the number it came from.

The fixed point is worse off. $ε_0$ has no notation in the system being drawn — that is its definition — so no figure here contains it. The tower figure shows four terms of a sequence climbing towards it, which is a picture of an approach and not of the thing approached, and the caption says so. This is a recurring limit in this field: the object being argued about is often exactly the one that cannot appear, and the honest figure draws the approach and labels it as an approach.

The last limitation is about depth. The tables print notation as a line of text, so a nesting of exponents three deep reads as a string with two carets in it. The object is a tree, the comparison walks it recursively, and a drawing that showed the tree would show the recursion better and fit fewer rows. Both are compromises; this one was chosen because the increase down the column is the property being asserted.

Where the ladder goes next #

Every limit ordinal in the tower figure was approached by a sequence — $ω$ by the whole numbers, $ω^ω$ by the powers of $ω$. The sequences all had length $ω$, and it is natural to assume that is what a limit is. It is not. There are ordinals that no sequence of length $ω$ reaches, and the smallest of them is the first uncountable ordinal, which is the next rung.