Reached from below, or not at all

An ordinal is either zero, one step past another, or a limit — and a limit is described as the least thing above everything below it. That description is passive. The active question is how a limit is reached, and the answer distinguishes ordinals in a way that size does not.

Fundamental sequences #

For every limit ordinal in the figure there is an increasing sequence of smaller ordinals whose supremum it is, indexed by the whole numbers. Such a sequence is called fundamental, and choosing one for every limit below $ε_0$ is routine: the normal form says how.

If the last term of the normal form is $ω^{β+1} \cdot c$ with $β + 1$ a successor exponent, replace that term by $ω^{β+1} \cdot (c-1) + ω^{β} \cdot n$ and let $n$ run. If the last exponent is itself a limit, recurse into it. Either way the terms increase, every term is below the ordinal, and the supremum is the ordinal — the three properties the figures assert on every ordinal they draw.

The choice of sequence is a convention rather than a theorem — many sequences have the same supremum, and the one above is merely the standard one. What is not a convention is that some sequence of that length exists, and that is the property this rung is about.

Cofinality #

Define the cofinality of an ordinal $α$ to be the least length of an increasing sequence whose supremum is $α$.

A successor has cofinality $1$: the sequence consisting of its predecessor alone reaches it. Every limit ordinal below $ε_0$ has cofinality $ω$, since the recipe above produces a sequence indexed by the whole numbers. In fact every countable limit ordinal has cofinality $ω$: list its elements — the same move that puts the fractions in a line — and take running maxima, discarding repetitions.

That last point is worth its own sentence, because it makes countable ordinals concrete objects rather than abstractions. Every countable ordinal embeds, order-preservingly, into the rationals. The rationals are the universal countable dense order, which is why they can absorb every countable order type at once; a line’s worth of points fitting into a segment is the same phenomenon on the side of size rather than of order. The picture above is such an embedding, done by squeezing; the general proof is an induction. So the whole of the ordinals up to and including $ε_0$ — every ordinal this ladder has drawn — lives inside a set as familiar as the fractions between zero and one.

The first one that cannot be reached #

Collect all the countable ordinals. They form a set, and being a set of ordinals it is itself an ordinal, called $ω_1$. It is uncountable — if it were countable it would be one of its own members, which no ordinal is — and every ordinal below it is countable, so it is the least uncountable one.

Now ask for a fundamental sequence. Suppose $α_0 < α_1 < α_2 < \dots$ were countably many countable ordinals with supremum $ω_1$. Each $α_k$ is a countable set of ordinals, so their union is a countable union of countable sets, hence countable; and the supremum of the sequence is the order type of that union, so it is a countable ordinal. It cannot be $ω_1$.

So $ω_1$ is a limit ordinal that no sequence of length $ω$ reaches. Its cofinality is $ω_1$ itself — climbing to it requires uncountably many steps, and no shortcut exists.

An ordinal equal to its own cofinality is called regular. Both $ω$ and $ω_1$ are regular; and the interesting fact is that not every uncountable ordinal is.

Where $ω_1$ comes from without choosing anything #

The construction of $ω_1$ above — collect all the countable ordinals — sounds as though it needs the ability to well-order things, and it does not. That is worth separating out, because the axiom of choice arrives two paragraphs later and it would be easy to think it was here too.

Hartogs’ construction is the careful version. Given any set $X$, consider all the well-orderings of subsets of $X$; each has an order type; those order types form a set of ordinals, and the least ordinal not among them exists. Applied to the natural numbers it gives an ordinal that does not inject into them — which is to say, an uncountable one — and the least such is $ω_1$. No choosing is involved: the well-orderings being collected are the ones that happen to exist, and nothing is asserted about whether $X$ itself carries one.

So $ω_1$ exists in plain set theory, is uncountable in plain set theory, and every ordinal below it is countable in plain set theory. The three facts this rung is built on are secure. What is not secure without choice is the regularity, and the reason is that regularity is a statement about every countable sequence at once rather than about the ordinals individually.

This is a distinction the collection meets elsewhere in the same shape. The existence of a choice function is not needed to talk about the objects being chosen from; it is needed to talk about all of them simultaneously, and the theorems that quietly fail without it are the theorems with a “for every countable family” in them.

Singular ordinals: large and easy to reach #

Take the sequence of infinite cardinals $ℵ_0, ℵ_1, ℵ_2, \dots$, one for each whole number, and let $ℵ_ω$ be the supremum. It is uncountable — vastly larger than $ω_1$ — and it is the supremum of a sequence of length $ω$. Its cofinality is $ω$.

That is the shape worth carrying away. Size and cofinality are independent: an ordinal can be enormous and still be the end of an ordinary countable climb, or comparatively small and reachable only by an uncountable one. What decides it is not how many elements are below, but whether they can be exhausted by a short increasing walk.

Regular, singular, and the induction that has to change #

The distinction earns its keep in how arguments are written, not only in how ordinals are catalogued.

An induction along the ordinals has three cases, and the limit case says: if the property holds everywhere below $λ$ then it holds at $λ$. For a limit of cofinality $ω$ that hypothesis can be used along a sequence — check the property at $α_0, α_1, α_2, \dots$ and conclude it at the supremum — and a great many arguments are written exactly that way, because a sequence is something a proof can iterate over.

At an ordinal of uncountable cofinality that move is unavailable, and the substitute is genuinely different: a property that holds on a club — a closed unbounded subset — is what an argument gets to work with, and closed unbounded sets at $ω_1$ have the pleasant feature that countably many of them still intersect. That closure property is a direct consequence of regularity, and it is why $ω_1$ is the smallest place where the machinery of stationary sets is worth building.

The practical summary is short. Below $ε_0$, and indeed below $ω_1$, every limit is the end of a countable climb and a proof may induct along one. At $ω_1$ and at every regular uncountable ordinal, it may not, and the argument has to be rebuilt around sets rather than sequences. Which of the two situations obtains is exactly the cofinality, and nothing about the size of the ordinal announces it — the arithmetic of sizes is blind to the distinction, since it identifies every countable ordinal with a single cardinal and cannot see how any of them is approached.

What it costs, and the axiom underneath #

The argument that $ω_1$ is regular used a step that is worth flagging: a countable union of countable sets is countable. Proving it requires choosing, for each of countably many sets, a listing of that set — countably many choices at once, with no rule given for making them.

That is the axiom of choice, in its countable form, and it is not decoration here. Feferman and Lévy built a model of set theory without choice in which the real numbers are a countable union of countable sets, and in which $ω_1$ has cofinality $ω$. Everything else in that model is ordinary: $ω_1$ is still the least uncountable ordinal, still uncountable, and now reachable by a countable climb.

So “is $ω_1$ regular?” is not a fact about the ordinal at all. It is a fact about how much choosing the surrounding theory permits, which is the same discovery this collection’s essays on independence keep arriving at from different directions: the question with no answer from the axioms is the normal case rather than the exception, once the questions get past the countable.

The gap between the countable and the first uncountable #

One more consequence, because it is the fact that makes $ω_1$ feel strange rather than merely large.

Below $ω_1$ sit the countable ordinals: $ω$, $ω^ω$, $ε_0$, and an enormous supply past every notation system anybody has built. Every one of them is the order type of a subset of the rationals. Above them all sits $ω_1$, and nothing is between — it is the least uncountable ordinal, so there is no ordinal that is uncountable and smaller.

That means the climb from the countable to the uncountable has no intermediate stage to pass through, and yet cannot be made in countably many steps. Any increasing countable sequence of countable ordinals stops short, always, however cleverly chosen — and the shortfall is not small: the supremum of such a sequence is still countable, so the sequence has not merely failed to arrive, it has not left the countable region at all.

Compare that with the ordinary limits of this ladder. Approaching $ω^ω$ by $ω, ω^2, ω^3, \dots$ passes through the region below it and gets arbitrarily close in the only sense available. Approaching $ω_1$ from below is not a matter of getting close; there is no notion of close, and every countable attempt lands in the same place it started from. Whether that is a fact about the ordinals or about the theory’s power to choose is what the section above settles: with choice it is a fact about the ordinals, and without choice it may fail entirely.

The same barrier, one level down #

There is a second ordinal that cannot be reached from below, and it is countable — which makes it the sharper example, because the obstruction is not size at all.

Every countable ordinal has a fundamental sequence, as the section above established. Ask instead for a computable one: a sequence a machine could enumerate, with the comparison between terms decidable. Every ordinal this ladder has drawn has one — $ω$, $ω^ω$, $ε_0$, everything the normal form names, because the recipe for the sequence is itself a short program.

Collect the ordinals that do. They are the ones with a computable well-ordering of the whole numbers as their order type, they form a countable set, and the least ordinal not among them is called $ω_1^{\mathrm{CK}}$, after Church and Kleene. It is countable — being the supremum of countably many countable ordinals — so it has a fundamental sequence of length $ω$, and no computable one. Any sequence climbing to it must be uncomputable, because a computable one would make the ordinal computable.

The parallel with $ω_1$ is exact and the difference is the point. $ω_1$ is not reachable by any countable climb; $ω_1^{\mathrm{CK}}$ is reachable by a countable climb and by no describable one. Both are limits with nothing between them and what lies below, both are barriers of the same shape, and only one of them is about cardinality.

This is where every notation system in this collection eventually stops. Cantor normal form runs out at $ε_0$; adding symbols for $ε_0$ and its successors pushes the ceiling up; the Veblen functions push it further; and every such system, being a system, names computably many ordinals and therefore cannot reach $ω_1^{\mathrm{CK}}$. The ceiling is not an artefact of any particular notation. It is the supremum of all of them, and it is a countable ordinal that no machine can name.

That has a consequence for the theme of the rung below this one. The ordinal measuring a formal system’s strength is always below $ω_1^{\mathrm{CK}}$ — a proof of well-foundedness has to be written down, so the ordering has to be describable — so the whole enterprise of ordinal analysis takes place inside a countable region that is itself bounded by an unreachable countable ordinal. Every system anybody strengthens has its own ordinal, each is larger than the last, and the sequence of them cannot be continued past a barrier that has nothing to do with infinity and everything to do with what can be written.

So the essay’s title admits two readings, and both are theorems. An ordinal may be out of reach because every climb to it is too short — that is $ω_1$, and it is about cardinality. Or it may be out of reach because every climb to it is too complicated to state — that is $ω_1^{\mathrm{CK}}$, and it is about description. The second barrier arrives long before the first, and every ordinal this ladder can draw sits below both.

Where cofinality bites: the continuum #

Cofinality would be a taxonomy if it were not for one theorem, and the theorem is the reason it appears in every serious treatment.

König’s theorem, in the form that matters here: the cofinality of $2^{ℵ_0}$ is greater than $ℵ_0$. So whatever the size of the continuum is, it is not the supremum of a countable increasing sequence of smaller cardinals — which immediately rules out an infinite family of candidates. The continuum cannot be $ℵ_ω$, and cannot be $ℵ_{ω_1 \cdot 2}$ or any other cardinal of countable cofinality.

That is a genuine constraint, and it is nearly the only one. Easton’s theorem says that apart from monotonicity and this cofinality restriction, the continuum function can be almost anything the axioms are consulted about: $2^{ℵ_0}$ may consistently be $ℵ_1$, or $ℵ_2$, or $ℵ_{17}$, or $ℵ_{ω+1}$. The continuum hypothesis is the guess that it is the first of those, and the axioms decide none of it.

So the ordinal-theoretic fact — how a limit is approached — turns out to be the only structural fact about the continuum that the axioms deliver. It is a small return, and it is not nothing, and it came from asking a question about arrangements rather than about sizes.

A note on the name, since two theorems in this collection carry it. König’s lemma — every infinite finitely-branching tree has an infinite path — is Dénes Kőnig’s, from 1927. König’s theorem about cofinality is Julius König’s, from 1905. They are different people and different results, and the coincidence has confused readers for a century.

What the pictures cannot show #

$ω_1$ does not appear in any figure on this page, and it cannot. Every drawing here is a finite set of marks standing for a countable ordinal, and the whole content of the section about $ω_1$ is that no such approximation approaches it — a picture of five terms climbing towards $ω_1$ would be a picture of a countable ordinal with a misleading label on the right-hand end.

That is the sharpest case of a limitation this field runs into constantly. The figures can draw the objects with fundamental sequences, because a fundamental sequence is exactly a recipe for drawing finitely many terms and asserting the rest. An ordinal of uncountable cofinality supplies no such recipe, and the honest response is prose.

What the figures do check is the half that can be checked. Every term of every sequence drawn was compared against the ordinal it approaches and against its predecessor, using the ordinal comparison rather than the drawing — so the claim that these are increasing sequences below their limits is verified, at every parameter any essay uses, rather than illustrated.

And the embedding into the rationals is real rather than decorative. The marks sit at $1 - 1/(k+1)$ and at the analogous positions inside each block, which are rational numbers, and the order of the marks along the line is the order of the ordinal. What no drawing can do is the same for $ω_1$: an uncountable well-ordered set does not fit inside the real line in order, let alone inside the rationals, and the reason is exactly the countability of the gaps.

Where the ladder goes next #

Fundamental sequences were introduced here as a way of describing how a limit is approached. They have a second use, and it is the one that closes this ladder: they turn an ordinal into a growth rate. Define a function at each ordinal by iterating the previous one, and take the fundamental sequence at limits, and the ordinal becomes a measure of how fast a function can grow — which is how the enormous number of steps in a Goodstein sequence is stated exactly rather than described as unimaginable.