nLab
countable ordinal

Contents

Context

Foundations

Mathematics

Contents

Idea

In classical mathematics, a countable ordinal is the order type? of a well-ordered set whose cardinality is countable (i.e., either finite or denumerable).

Countable ordinals play an important role in recursion theory, computability theory, and in proof theory, where they are used for example to measure the consistency strength of formal theories via ordinal analysis. They also play a role in philosophy of mathematics, for example to discuss what it means for a notion to be “predicative”.

Definitions

As indicated above, countable ordinals can be defined structurally as countable well-ordered sets (or “wosets”). As is the case with any ordered set, a woset WW can be regarded as a coalgebra over the covariant power-set functor,

θ:WP(W)\theta: W \to P(W)
\,
x{y:y<x}.x \mapsto \{y: y \lt x\}.

A coalgebra map f:WWf: W \to W' between wosets, aka a simulation, amounts to an inclusion of the domain as an initial segment of the codomain.

The category of countable wosets and simulations, thus ordered by inclusion, is a preorder and in fact equivalent to a woset. In material set theory, this woset is often identified with the first uncountable ordinal (well-ordered set under the membership relation), often denoted ω 1\omega_1. Structurally, we can define ω 1\omega_1 up to isomorphism as a skeleton of the category of countable ordinals, and so the study of countable ordinals becomes a study of the order structure of ω 1\omega_1.

This ω 1\omega_1 has no top element (of course not: otherwise ω 1\omega_1 would be a countable ordinal), and much of the interest and fun of the subject lies in playing the childhood game of seeing who can name the bigger number, or in this case the bigger countable ordinal. A key fact is that ω 1\omega_1 is countably cocomplete, and therefore behaves like a self-contained universe with respect to countably cocontinuous operations. There is quite a lot of scope in what one can build up to using such operations. After playing the larger ordinal game for a while, and becoming impressed by the sizes of ordinals one can define – while recognizing at the same time that one is “never getting anywhere” relative to ω 1\omega_1 itself – it is hard not to become awestruck by the staggering immensity of ω 1\omega_1.

Anyone who is unimpressed by the size of large countable ordinals has almost surely never seriously played with them. For that matter, people who are unimpressed by large finite numbers have probably never played around with them either, or at least not all that imaginatively! (And interestingly, one can use large countable ordinals reflectively to construct enormous integers, or one can use large uncountable ordinals reflectively to construct enormous countable ordinals.)

Fixed points and the Veblen hierarchy

Here we discuss the use of fixed point theory in describing the lower stages of the Veblen hierarchies of countable ordinals, which will lead up to the Feferman-Schütte ordinal. We freely allow ourselves to reason classically and use the principle of excluded middle.

The ordinal ω 1\omega_1 is countably cocomplete, and we are primarily interested in functors or order-preserving maps f:ω 1ω 1f: \omega_1 \to \omega_1 that preserve colimits of countable (finite or denumerable) diagrams – or countable chains, without loss of generality. We’ll call such maps continuous, for short. If xf(x)x \leq f(x) for all xω 1x \in \omega_1, then we say that ff is inflationary.

Preservation of colimits of finite nonempty chains comes for free, so we can ignore that. The colimit of the empty chain is the bottom element 00, and we will make a point of including preservation of that.

The first result is a baby form of a general theorem due to Adámek on initial algebras of endofunctors.

Proposition

Suppose f:ω 1ω 1f: \omega_1 \to \omega_1 is inflationary and continuous. Then every xω 1x \in \omega_1 has an upper bound that is a fixed point under ff.

Proof

For any xx, the colimit xx' of xf(x)f 2(x)x \leq f(x) \leq f^2(x) \leq \ldots exists, and since ff preserves countable colimits, xx' is a fixed point of ff.

Lemma

If f:ω 1ω 1f: \omega_1 \to \omega_1 is order-preserving and satisfies f(β)=sup{f(α):α<β}f(\beta) = \sup \{f(\alpha): \alpha \lt \beta\} for all limit (i.e., non-successor) ordinals β\beta, then ff is continuous.

The converse of this result is trivially true.

Proof

For the case β=0\beta = 0, the set {f(α):α<β}\{f(\alpha): \alpha \lt \beta\} is empty and thus has 00 as its supremum, so f(0)=0f(0) = 0.

Suppose that β\beta is the colimit of a chain x 1x 2x_1 \leq x_2 \leq \ldots with countably infinite image. Then this chain is cofinal in the set {α:α<β}\{\alpha: \alpha \lt \beta\}, and similarly f(x 1)f(x 2)f(x_1) \leq f(x_2) \leq \ldots is cofinal in {f(α):α<β}\{f(\alpha): \alpha \lt \beta\}. Therefore the colimit of this chain is the same as the supremum of {f(α):α<β}\{f(\alpha): \alpha \lt \beta\}, which is f(β)f(\beta).

Proposition

Suppose f:ω 1ω 1f: \omega_1 \to \omega_1 is inflationary and continuous. Define f:ω 1ω 1f': \omega_1 \to \omega_1 to be the function that takes each xω 1x \in \omega_1 to the least fixed point of ff that is greater than f(y)f'(y) for all y<xy \lt x. Then ff' is also inflationary and continuous.

Proof

By definition, f(y)<f(x)f'(y) \lt f'(x) whenever y<xy \lt x, so ff' is order-preserving. That ff' is inflationary is proved by induction: given that αf(α)\alpha \leq f'(\alpha) for all α<β\alpha \lt \beta, we have αf(α)<f(β)\alpha \leq f'(\alpha) \lt f'(\beta) i.e. α<f(β)\alpha \lt f'(\beta) for all α<β\alpha \lt \beta, whence βf(β)\beta \leq f'(\beta). To prove ff' is continuous, let β\beta be a non-successor; by continuity of ff we have

f(sup{f(α):α<β})=sup{f(f(α)):α<β}=sup{f(α):α<β}f(\sup \{f'(\alpha): \alpha \lt \beta\}) = \sup \{f(f'(\alpha)): \alpha \lt \beta\} = \sup \{f'(\alpha): \alpha \lt \beta\}

so that this supremum is in fact a fixed point of ff, and thus the least fixed point of ff greater than every f(α)f'(\alpha) for α<β\alpha \lt \beta. It therefore follows by definition of ff' that

f(β)=sup{f(α):α<β}f'(\beta) = \sup \{f'(\alpha): \alpha \lt \beta\}

and so, by the preceding lemma, ff' is continuous.

Definition

The Veblen hierarchy is a family of functions f α:ω 1ω 1f_\alpha: \omega_1 \to \omega_1, one for each αω 1\alpha \in \omega_1, defined as follows.

  • Define f 0:ω 1ω 1f_0: \omega_1 \to \omega_1 by f 0(x)=sup{y+2:y<x}f_0(x) = \sup \{y+2: y \lt x\}.

This is inflationary, and continuous by the lemma.

  • Then define f α:ω 1ω 1f_\alpha: \omega_1 \to \omega_1 by f α+1=f α f_{\alpha + 1} = f_\alpha^' and f β=sup α<βf αf_\beta = \sup_{\alpha \lt \beta} f_\alpha at limit ordinals β>0\beta \gt 0.

By induction and the preceding proposition, f αf_\alpha is inflationary and continuous at successor cardinals α\alpha, and also at limit cardinals α>0\alpha \gt 0 since countable colimits of inflationary and continuous maps are also inflationary and continuous.

It is worth contemplating the growth of the first few f αf_\alpha. For f 0f_0, we have f 0(α)=α+1f_0(\alpha) = \alpha + 1 if α\alpha is a successor, and f 0(α)=αf_0(\alpha) = \alpha if α\alpha is a limit ordinal.

This means that next we have f 1(0)=0f_1(0) = 0, f 1(1)=ωf_1(1) = \omega, f 1(2)=2ωf_1(2) = 2 \omega, …, f 1(ω)=ω 2f_1(\omega) = \omega^2, and so on. The first fixed point past 00 is at x=ω ωx = \omega^\omega.

Next, we have f 2(0)=0f_2(0) = 0, f 2(1)=ω ωf_2(1) = \omega^\omega, f 2(2)=ω 2ωf_2(2) = \omega^{2\omega}, …, f 2(ω)=ω ω 2f_2(\omega) = \omega^{\omega^2}, and so on. The first fixed point past 00 is the same as the first fixed point of xω xx \mapsto \omega^x (a countably iterated exponential stack), typically denoted as ϵ 0\epsilon_0.

We pause to note that ϵ 0\epsilon_0 is sometimes considered the first reasonable thing to call a “large countable ordinal”. An ordinal analysis first carried by by Gerhard Gentzen asserts, roughly speaking, that the consistency of Peano arithmetic is provable from primitive recursive arithmetic (which is weaker than PA) augmented by the principle of induction up to ϵ 0\epsilon_0.

Pressing on, we have f 3(0)=0f_3(0)= 0, f 3(1)=ϵ 0f_3(1) = \epsilon_0, f 3(2)=ϵ 1f_3(2) = \epsilon_1 (the first fixed point of xω xx \mapsto \omega^x past ϵ 0\epsilon_0), and so on. The first fixed point past 00 of f 3f_3 is the limit of ϵ 0,ϵ ϵ 0,ϵ ϵ ϵ 0,\epsilon_0, \epsilon_{\epsilon_0}, \epsilon_{\epsilon_{\epsilon_0}}, \ldots, sometimes indicated by an infinite descending stack of subscripts ϵ\epsilon. This ordinal is of size that far, far surpasses any human powers of visualization.

And clearly we are only just getting started. Each successive f n(1)f_n(1) dwarfs its predecessor f n1(1)f_{n-1}(1) to an indescribable degree. To speak nothing of f ω(1)f_\omega(1), and so on.

Ordinal notations and the Feferman-Schütte ordinal

Despite such colossal sizes, it is possible to effectively notate such ordinals using nothing more than finite binary trees, all the way up to the Feferman-Schütte ordinal, which seems to be the first of the “large countable ordinals” that the experts consider big enough to honor with human names. (There are others much further down the pike, such as the Bachmann-Howard ordinal or the considerably larger, almost godlike Church-Kleene ordinal.)

Before introducing this, we prove the following lemmas.

Lemma

If α<β\alpha \lt \beta, then every value f β(x)f_\beta(x) is a fixed point of f αf_\alpha.

Proof

This is clear if α+1=β\alpha + 1 = \beta. Suppose f γ(x)f_\gamma(x) is a fixed point of f αf_\alpha whenever α<γ<β\alpha \lt \gamma \lt \beta. If β\beta is a successor γ+1\gamma + 1, then we have

f β(x)=f γ(f β(x))=f α(f γ(f β(x)))=f α(f β(x)),f_\beta(x) = f_\gamma(f_\beta(x)) = f_\alpha(f_\gamma(f_\beta(x))) = f_\alpha(f_\beta(x)),

and if β\beta is a limit, then

f α(f β(x))=f α(sup α<γ<βf γ(x))=sup α<γ<βf α(f γ(x))=sup α<γ<βf γ(x)=f β(x)f_\alpha(f_\beta(x)) = f_\alpha(\sup_{\alpha \lt \gamma \lt \beta} f_\gamma(x)) = \sup_{\alpha \lt \gamma \lt \beta} f_\alpha(f_\gamma(x)) = \sup_{\alpha \lt \gamma \lt \beta} f_\gamma(x) = f_\beta(x)

which completes the proof.

Lemma

For all yω 1y \in \omega_1, we have yf y(1)y \leq f_y(1).

Proof

By induction. Suppose αf α(1)\alpha \leq f_\alpha(1) for all α<β\alpha \lt \beta. Since 1f β(1)1 \leq f_\beta(1), we have

αf α(1)f α(f β(1))=f β(1)\alpha \leq f_\alpha(1) \leq f_\alpha(f_\beta(1)) = f_\beta(1)

since f β(1)f_\beta(1) is by the preceding lemma a fixed point of f αf_\alpha. Since f β(1)f_\beta(1) is both a limit ordinal and an upper bound for every α<β\alpha \lt \beta, it follows that βf β(1)\beta \leq f_\beta(1).

Notice that by definition, f β(γ)f_\beta(\gamma) is continuous in the argument β\beta, since we defined f β=sup α<βf αf_\beta = \sup_{\alpha \lt \beta} f_\alpha at limit ordinals β\beta. Therefore the function xf x(1)x \mapsto f_x(1) is inflationary (by lemma ) and continuous. Applying proposition , it has a least fixed point. This fixed point is called the Feferman-Schütte ordinal, denoted by Γ 0\Gamma_0.

Theorem

If α>0\alpha \gt 0 is less than Γ 0\Gamma_0, then there exist β,γ\beta, \gamma, both less than α\alpha, such that α=f β(γ)\alpha = f_\beta(\gamma).

Proof

If α\alpha is not a limit ordinal, then α=γ+1\alpha = \gamma + 1 and hence α=f 0(γ)\alpha = f_0(\gamma). Obviously α\alpha cannot be a value of f βf_\beta for β>0\beta \gt 0, since all such values are limit ordinals.

If α\alpha is a limit ordinal and α<Γ 0\alpha \lt \Gamma_0, then there is some β<α\beta \lt \alpha for which α\alpha is not a fixed point of f βf_\beta. Otherwise we would have f β(α)=αf_\beta(\alpha) = \alpha for all β<α\beta \lt \alpha, and this would force f α(α)=αf_\alpha(\alpha) = \alpha (by definition of f αf_\alpha). And in that case

αf α(1)f α(α)=α\alpha \leq f_\alpha(1) \leq f_\alpha(\alpha) = \alpha

so that α\alpha is a fixed point of xf x(1)x \mapsto f_x(1), contradicting α<Γ 0\alpha \lt \Gamma_0.

Thus, for α\alpha a limit ordinal, take β\beta to be the least ordinal such that α<f β(α)\alpha \lt f_\beta(\alpha). Note that β\beta is a successor, β=β+1\beta = \beta' + 1, because we have α=f γ(α)\alpha = f_\gamma(\alpha) for any γ<β\gamma \lt \beta, and this would imply α=f β(α)\alpha = f_\beta(\alpha) if β\beta were a limit.

We have αf β(γ)\alpha \leq f_\beta(\gamma) for some γ<α\gamma \lt \alpha (for if f β(γ)<αf_\beta(\gamma) \lt \alpha for all γ<α\gamma \lt \alpha, we could infer α\alpha is a fixed point of f βf_\beta). Let γ\gamma be the least ordinal (less than α\alpha) such that αf β(γ)\alpha \leq f_\beta(\gamma). Then in fact this last inequality is an equality. For suppose γ=δ+1\gamma = \delta + 1; then by definition of γ\gamma, we have

f β(δ)=f β+1(δ)<αf_\beta(\delta) = f_{\beta' + 1}(\delta) \lt \alpha

and we also have that α=f β(α)\alpha = f_{\beta'}(\alpha) by definition of β\beta. Since f β(γ)=f β+1(γ)=f β+1(δ+1)f_\beta(\gamma) = f_{\beta' + 1}(\gamma) = f_{\beta' + 1}(\delta + 1) is by definition the least f βf_{\beta'}-fixpoint greater than f β+1(δ)f_{\beta' + 1}(\delta), we immediately infer f β(γ)αf_\beta(\gamma) \leq \alpha, as required. If on the other hand γ\gamma is a limit, we have

f β(δ)<αf_\beta(\delta) \lt \alpha

for all δ<γ\delta \lt \gamma, and we again infer f β(γ)αf_{\beta}(\gamma) \leq \alpha, as required.

This theorem gives a canonical finite binary tree representation of any α<Γ 0\alpha \lt \Gamma_0, by recursion. The binary tree τ(0)\tau(0) of 00 consists of just 00 as root, with no child-pair. Given that every β\beta less than α\alpha has been assigned a binary tree τ(β)\tau(\beta), we define τ(α)\tau(\alpha) to have the child-pair (τ(β),τ(γ))(\tau(\beta), \tau(\gamma)) where

  • β\beta is the least ordinal less than α\alpha such that α<f β(α)\alpha \lt f_\beta(\alpha), and

  • γ\gamma is the least ordinal less than α\alpha such that αf β(γ)\alpha \leq f_\beta(\gamma).

The resulting binary tree τ\tau is finite for every α<Γ 0\alpha \lt \Gamma_0, since it has binary branching and there are no infinite branches or paths up the tree (since that would yield an infinite descent α>α 1>α 2>\alpha \gt \alpha_1 \gt \alpha_2 \gt \ldots with no least element, contradicting well-orderedness).

This finite binary tree notation is one of many possible ordinal notations for naming countable ordinals. It is more expressive the Cantor normal form that provides a notation for ordinals α\alpha less than ϵ 0\epsilon_0, where one writes α\alpha uniquely in the form

α=ω β+γ\alpha = \omega^\beta + \gamma

with β,γ<α\beta, \gamma \lt \alpha and γ<γ+ω β\gamma \lt \gamma + \omega^\beta, and continues recursively.

Remark

However, Cantor normal form has the virtue of uniqueness. For the binary operation (β,γ)f β(γ)(\beta, \gamma) \mapsto f_\beta(\gamma), it is possible to have two distinct pairs (β,γ)(\beta, \gamma), (β,γ)(\beta', \gamma') which are equivalent in the sense that

f β(γ)=f β(γ);f_\beta(\gamma) = f_{\beta'}(\gamma');

we counteracted this by using the pair (β,γ)(\beta, \gamma) which was least in its equivalence class with respect to lexicographic order.

Fundamental sequences and the Bachmann-Howard ordinal

Fast-growing functions on \mathbb{N}

Recursive ordinals

Of course, having reached Γ 0\Gamma_0 as the least fixed point of xf x(1)x \mapsto f_x(1), there is nothing stopping one from starting all over again with a new Veblen hierarchy, defining g 0(x)=f x(1)g_0(x) = f_x(1) and defining g αg_\alpha analogously to how we defined f αf_\alpha.

In one or another way we can continue extending ordinal notation schemes, but all such schemes are recursive by definition, and at some point we cannot go any further:

Definition

A countable ordinal α\alpha is recursive if there is a computable relation on \mathbb{N} (or a recursive subset of ×\mathbb{N} \times \mathbb{N}) that well-orders \mathbb{N}, so that the resulting woset is isomorphic to α\alpha.

There are countably many computable relations on \mathbb{N}, and so the supremum of the recursive ordinals in ω 1\omega_1 exists. It is called the Church-Kleene ordinal. It is the first non-recursive ordinal.

References

For a light-hearted introduction with many useful references, see

  • John Baez, Week 236, This Week’s Finds in Mathematical Physics, July 26, 2006. (web)

A very readable account of countable ordinals up to the Feferman-Schütte ordinal is

  • Jean Gallier, What’s so Special about Kruskal’s Theorem and the Ordinal Γ 0\Gamma_0?, A Survey of Some Results in Proof Theory, Annals of Pure and Applied Logic, Vol. 53, 199-260 (1991). (Part II)

An application of coalgebra theory to ordinal notation systems is described here:

  • Peter Hancock, Ordinal notation systems. (web)

Ordinal analysis as measuring consistency strengths of theories is well-described in this paper:

  • Michael Rathjen, The art of ordinal analysis, International Congress of Mathematicians, II, Eur. Math. Soc., Zurich, pp. 45–69. (pdf)

Last revised on November 7, 2018 at 07:24:52. See the history of this page for a list of all contributions to it.