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.

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.