One step in front of infinitely many

The sequence that explodes and still stops used ordinals as a measuring stick and said almost nothing about them as objects. They have an arithmetic, and it is the first arithmetic most readers meet in which the order of the operands matters — not as a technicality but as the entire content.

An ordinal is an order type: what is left of a well-ordered set when the identity of its elements is forgotten and only the shape of the ordering is kept. A well-ordering is one in which every non-empty part has a least element, which is exactly the condition that makes an infinite descent impossible and is therefore the condition every termination argument in this collection eventually rests on. The natural numbers in their usual order give $ω$. Adding is concatenation — $α + β$ is the order type of a copy of $α$ with a copy of $β$ laid after it — and once addition is that, the asymmetry is unavoidable, because laying one thing after another is not a symmetric operation.

Where the asymmetry comes from #

Put a single step in front of the natural numbers: an element $\star$, then $0, 1, 2, \dots$. Rename $\star$ as $0$ and each $n$ as $n+1$, and the result is the natural numbers again. The order type has not changed. So $1 + ω = ω$.

Put the step after instead: $0, 1, 2, \dots$, then $\star$. Now there is an element with infinitely many things below it and nothing between them and it. The natural numbers have no such element, and an order-preserving relabelling cannot create one, so this is a different order type: $ω + 1$.

The absorbing on the left is not a quirk of $1$. Any ordinal placed in front of $ω$ vanishes into it as long as it is smaller — $5 + ω = ω$, and $ω + ω$ placed in front of $ω^2$ is invisible — because a finite or shorter initial segment can be absorbed by relabelling. What survives a sum is always the tail.

Multiplication, and which convention it follows #

The product $α \cdot β$ is $β$ copies of $α$ laid end to end. That convention is not universal, and it is the one under which the notation $ω \cdot 2$ means what its shape suggests: two copies of $ω$, one after the other, which is $ω + ω$.

Take the copies the other way round: $2 \cdot ω$ is $ω$ copies of a two-element block. Written out, that is $a_0 b_0 a_1 b_1 a_2 b_2 \dots$ — a sequence of steps with nothing after them all, which is $ω$ again. So one product is bigger than the other, and it is the one with the infinite factor on the right.

The general rule is the same as for sums, one level up. Multiplying on the right by an infinite ordinal reaches past whatever finite structure was there, and multiplying on the left preserves it. The whole of ordinal arithmetic is that sentence and its consequences.

Which laws survive #

It is easy to conclude from the above that nothing survives, and worth being precise about what does.

Associativity holds, for both operations. Concatenating three blocks does not care where the brackets go, and the figure below checks the two bracketings of a sum that includes an absorbing step.

Left distributivity holds: $α \cdot (β + γ) = α \cdot β + α \cdot γ$, because $β + γ$ copies of $α$ is $β$ copies followed by $γ$ copies.

Right distributivity fails, and the counterexample is the smallest one available. $(1 + 1) \cdot ω$ is $2 \cdot ω$, which is $ω$; while $1 \cdot ω + 1 \cdot ω$ is $ω + ω$, which is $ω \cdot 2$. The hero figure computes both.

Left cancellation holds — if $α + β = α + γ$ then $β = γ$ — and right cancellation fails, since $1 + ω = 2 + ω$ with $1 \neq 2$.

Subtraction exists on one side only. Given $α \le β$ there is exactly one $γ$ with $α + γ = β$, so the left summand can be removed. The right one cannot: nothing added to anything gives $ω$ from $ω + 1$, because sums only grow.

Exponentiation exists and behaves the same way. $ω^2$ is $ω \cdot ω$, which is $ω$ runs each of length $ω$; $2^ω$ is the limit of $2, 4, 8, \dots$, which is $ω$. So the base absorbs on the left here too, and the notation $ω^α$ is the one that grows. The order type behind $ω^α$ can be described directly — it is the finite sequences of smaller ordinals, ordered by their leading differences — but nothing in this essay needs that description, and the recursion is the honest way to read it: $ω^{α+1} = ω^α \cdot ω$, and at a limit the exponent takes the supremum of what is below.

That list is the honest summary, and its shape is worth noticing. Everything that fails, fails because addition is concatenation and concatenation notices which side is which. Nothing fails for a subtler reason.

What the arithmetic is keeping #

This collection has an essay on the other infinite arithmetic — the arithmetic of sizes — and the contrast between the two is the best argument for why ordinals are worth having.

Cardinal arithmetic is commutative and associative, and it is nearly trivial once anything infinite is involved: $ℵ_0 + 1 = ℵ_0$, $ℵ_0 + ℵ_0 = ℵ_0$, $ℵ_0 \cdot ℵ_0 = ℵ_0$. Every one of those is a bijection, and the price of having them is that subtraction and division become meaningless, since the answer would not be unique.

Ordinal arithmetic keeps what cardinal arithmetic throws away. The sets underlying $ω$, $ω + 1$, $ω \cdot 2$ and $ω^2$ are all countable — every one of them can be listed — so as sizes they are one object. As order types they are four objects, and the arithmetic can tell them apart because the arithmetic is about arrangements rather than counts.

The cost is exactly the commutativity. That trade — an operation that remembers more and commutes less — is the same one multiplication of quaternions makes to remember the order of rotations, and the same one function composition makes for the same reason. An operation that forgets which side its operands came from cannot record an order, and recording an order is what these objects are for.

There is a commutative alternative, and it is instructive that it exists and is not the default. The natural sum — add the Cantor normal forms termwise, as though they were polynomials in $ω$ — is commutative and associative, and it is used where an order is wanted for bookkeeping rather than for concatenation. It is not the sum defined by laying one order after another, so it answers a different question, and giving it the same symbol would be the mistake.

The same set, ordered four ways #

The order types above are not exotic objects requiring exotic sets. Every one of them can be put on the natural numbers, and doing so makes the arithmetic concrete.

Leave the natural numbers alone and the type is $ω$. Move $0$ to the end — order everything as usual, then declare $0$ larger than all of it — and the type is $ω + 1$, since there is now a last element with infinitely many below it. Put the evens in their usual order and then all the odds in theirs, and the type is $ω \cdot 2$: two runs, the second beginning after all of the first. Order by the exponent of two dividing a number and then by size within that, and the type is $ω^2$ — infinitely many runs, each infinite.

Four orderings, one set, four order types, and every one of them a well-ordering: every non-empty subset has a least element under each. The set never changed and nothing about it was counted differently. What changed was the arrangement, and the ordinals are exactly the invariant that arrangement has and the set does not.

This is the same move that makes a listable set meet every interval surprising, and it is worth stating the two facts side by side, because they pull in opposite directions and both are true. The rationals are countable, so they can be arranged in a sequence of type $ω$; the rationals in their usual order are not well-ordered at all, and have no ordinal. Being countable says an arrangement of type $ω$ exists; it says nothing about the arrangement the object arrived with.

So the arithmetic of this essay is an arithmetic of arrangements, and the reason it has to be more delicate than counting is that there are more arrangements than counts. There is one countable infinity, and there are uncountably many countable order types — which is the fact the next-but-one rung is about, and which is already visible here: $ω$, $ω+1$, $ω+2$, and so on past every finite step, then $ω \cdot 2$, and the list has barely started.

Successors, limits, and the third case in every induction #

An ordinal is one of three things: zero, a successor — one step past another — or a limit, with things below it but nothing immediately below.

That trichotomy is why induction along the ordinals has three cases where induction on the natural numbers has two. A property that holds at zero and passes from each ordinal to the next does not propagate past $ω$, because $ω$ is not the next anything: the step from below has to be supplied separately, as the statement that if the property holds at everything below a limit then it holds there too.

It is the same three-case shape that turns up wherever a structure is built from below rather than counted, including the tree arguments where the limit case is a branch rather than a supremum. The three-case structure is not decoration. It is precisely where Goodstein’s theorem gets its strength: the induction that proves it runs along the ordinals below $ε_0$, and the limit case is the one arithmetic cannot carry out for itself.

Where the arithmetic is actually used #

Two places, and both are about termination rather than about infinity.

The first is the one this ladder began with. A process that shrinks an ordinal at every step must stop, because the ordinals are well-ordered and an infinite descending sequence is impossible. To use that, the ordinal assigned to a state has to be computed, and computing it means adding and multiplying order types — which is why the arithmetic above is machinery rather than curiosity.

The hydra of the first rung is the clearest case. Chopping a head and letting the tree grow back changes the tree enormously and changes its ordinal by subtracting something, and the subtraction is exactly the operation this arithmetic supports on the left and refuses on the right. A measure that could be decreased in some places and increased in others would prove nothing; a measure that can only fall proves termination immediately. Which side of the sum the growth lands on is therefore the whole argument, and getting it right requires knowing that $ω^α \cdot n$ absorbs everything written after it.

The second is in proof theory, where an ordinal is attached to a formal system to say how much induction it can carry out — the measurement that makes a true sentence unprovable a matter of arithmetic strength rather than of cleverness. That is the subject of the last rung on this ladder, and the arithmetic here is the notation it is written in.

What the pictures cannot show #

The lines in these figures squeeze infinitely many steps into a finite width, which makes a limit point visible as a place where the marks pile up. That is a drawing convention and not a fact about the order type: the marks are at $1 - 1/(k+1)$ of the way along, and nothing in the ordinal knows about distance. Every generator here asserts the two things the convention has to respect — the marks strictly increase, and every limit mark has marks accumulating at it with nothing in the gap between — and no more than that.

The tables are worse behaved in an interesting way. They compare normal forms, and a normal form is a notation: two expressions are shown to be equal because the algorithm reduces them to the same list. That is a proof only if the reduction is right, so the figure carries a second, hand-written arithmetic for the ordinals below $ω^2$ and checks the general code against it in three hundred and eighty-four cases. Two implementations agreeing is evidence; one implementation asserting its own output is not.

What no figure here shows is a well-ordering. The objects being drawn are order types of well-ordered sets, and the well-ordering is the hypothesis rather than the picture — a line of marks is a picture of a sequence, and a sequence is well-ordered because it was built to be. That every set can be well-ordered at all is an axiom rather than a theorem, and nothing in this essay depends on it, because every ordinal drawn here was constructed explicitly.

Where the ladder goes next #

The expressions in the tables above were reduced to a normal form, and that reduction was used without being justified. It is a theorem: every ordinal is a descending sum of powers of $ω$ with whole-number coefficients, in exactly one way. That is base-$ω$ notation, it is what makes comparison mechanical, and it runs out at a specific place — the first ordinal too large to be written in terms of smaller ones — which is the ordinal that decides what arithmetic can prove.