Kerodon

$\Newextarrow{\xRightarrow}{5,5}{0x21D2}$ $\newcommand\empty{}$
$\Newextarrow{\xhookrightarrow}{10,10}{0x21AA}$

5.4.1 Ordinals and Well-Orderings

In this section, we review some standard facts about ordinals and well-ordered sets.

Definition 5.4.1.1. Let $(S, \leq )$ be a partially ordered set. We say that $(S,\leq )$ is well-founded if every nonempty subset $S_0 \subseteq S$ contains a minimal element: that is, an element $s \in S_0$ for which the set $\{ t \in S_0: t < s \} $ is empty.

Exercise 5.4.1.2. Let $(S, \leq )$ be a partially ordered set. Show that the following conditions are equivalent:

$(1)$

The partial order $\leq $ is well-founded: that is, every nonempty subset of $S$ contains a minimal element.

$(2)$

The set $Q$ does not contain an infinite descending sequence $s_0 > s_1 > s_2 > \cdots $.

Example 5.4.1.3. Every finite partially ordered set $(S, \leq )$ is well-founded.

Example 5.4.1.4. Let $S$ be any set, and let $\leq $ be the discrete partial ordering of $S$: that is, we have $s \leq t$ if and only if $s = t$. Then $(S, \leq )$ is well-founded.

Remark 5.4.1.5. Let $(S, \leq )$ be a well-founded partially ordered set. Then every subset $S_0 \subseteq S$ is also well-founded (when endowed with the partial order given by the restriction of $\leq $).

Definition 5.4.1.6. Let $(S, \leq )$ be a linearly ordered set. We say that $(S, \leq )$ is well-ordered if it is well-founded when regarded as a partially ordered set: that is, if every nonempty subset $S_0 \subseteq S$ contains a smallest element. In this case, we will refer to the relation $\leq $ as a well-ordering of the set $S$.

Definition 5.4.1.7 (Ordinals). An ordinal is an isomorphism class of well-ordered sets. If $(S, \leq )$ is a well-ordered set, then its isomorphism class is an ordinal which we will refer to as the order type of $S$.

Notation 5.4.1.8. We will typically use lower-case Greek letters to denote ordinals.

Example 5.4.1.9 (Finite Ordinals). Let $n$ be a nonnegative integer. Up to isomorphism, there is a unique linearly ordered set $S$ having exactly $n$ elements, which we can identify with the set $\{ 0 < 1 < \cdots < n-1 \} $. We will abuse notation by identifying $n$ with the order type of the linearly ordered set $S$. By means of this convention, we can view every nonnegative integer as an ordinal. We say that an ordinal $\alpha $ is finite it arises in this way (that is, if it is the order type of a finite linearly ordered set), and infinite if it does not.

Example 5.4.1.10. The set of nonnegative integers $\operatorname{\mathbf{Z}}_{\geq 0} = \{ 0 < 1 < 2 < \cdots \} $ is well-ordered (with respect to its usual ordering). Its order type is an infinite ordinal, which we denote by $\omega $.

By definition, well-ordered sets $(S, \leq )$ and $(T, \leq )$ have the same order type if there is an order-preserving bijection $f: S \xrightarrow {\sim } T$. We will show in a moment that in this case, the bijection $f$ is uniquely determined (Corollary 5.4.1.16). First, let us introduce a bit of additional terminology.

Definition 5.4.1.11. Let $(S, \leq )$ be a linearly ordered set. We say that a subset $S_0 \subseteq S$ is an initial segment if it is closed downwards: that is, for every pair of elements $s \leq s'$ of $S$, if $s'$ is contained in $S_0$, then $s$ is also contained in $S_0$. If $(T, \leq )$ is another linearly ordered set, we say that a function $f: S \hookrightarrow T$ is an initial segment embedding if it is an isomorphism (of linearly ordered sets) from $S$ to an initial segment of $T$.

Example 5.4.1.12. Let $(S, \leq )$ be a linearly ordered set. Then the identity morphism $\operatorname{id}_{S}: S \xrightarrow {\sim } S$ is an initial segment embedding.

Remark 5.4.1.13 (Transitivity). Let $(R, \leq )$, $(S, \leq )$, and $(T, \leq )$ be linearly ordered sets. Suppose that $f: R \hookrightarrow S$ and $g: S \hookrightarrow T$ are initial segment embeddings. Then the composition $(g \circ f): R \hookrightarrow T$ is also an initial segment embedding.

Proposition 5.4.1.14. Let $(S, \leq )$ and $(T, \leq )$ be linearly ordered sets, and let $f,f': S \hookrightarrow T$ be strictly increasing functions. Suppose that $S$ is well-ordered and that $f$ is an initial segment embedding. Then, for each $s \in S$, we have $f(s) \leq f'(s)$.

Proof. Set $S_0 = \{ s \in S: f'(s) < f(s) \} $. We wish to show that $S_0$ is empty. Assume otherwise. Since $S$ is well-ordered, there is a least element $s \in S_0$. Since $f$ is an initial segment embedding, the inequality $f'(s) < f(s)$ implies that we can write $f'(s) = f(t)$ for some $t < s$. Then $t \notin S_0$, so we must have $f(t) \leq f'(t)$. It follows that $f'(s) \leq f'(t)$, contradicting our assumption that the function $f'$ is strictly increasing. $\square$

Corollary 5.4.1.15 (Rigidity). Let $(S, \leq )$ and $(T, \leq )$ be linearly ordered sets, and let $f,f': S \hookrightarrow T$ be initial segment embeddings. If $S$ is well-ordered, then $f = f'$.

Corollary 5.4.1.16. Let $(S, \leq )$ and $(T, \leq )$ be well-ordered sets. If there exists an order-preserving bijection $f: S \xrightarrow {\sim } T$, then $f$ is unique.

Corollary 5.4.1.17. Let $(S,\leq )$ and $(T, \leq )$ be well-ordered sets. Then one of the following conditions is satisfied:

$(1)$

There exists an initial segment embedding $f: S \hookrightarrow T$.

$(2)$

There exists an initial segment embedding $g: T \hookrightarrow S$.

Proof. For each element $s \in S$, let $S_{\leq s}$ denote the initial segment $\{ s' \in S: s' \leq s \} $. Let $S_0 \subseteq S$ denote the collection of elements $s \in S$ for which there exists an initial segment embedding $f_{\leq s}: S_{\leq s} \hookrightarrow T$. Note that, if this condition is satisfied, then the morphism $f_{\leq s}$ is uniquely determined (Corollary 5.4.1.15). Moreover, if $s' \leq s$, then composite map $S_{\leq s'} \subseteq S_{\leq s} \xrightarrow { f_{\leq s} } T$ is also an initial segment embedding; it follows that $s'$ belongs to $S_0$, and $f|_{\leq s'}$ is the restriction of $f|_{\leq s}$ to $S_{\leq s'}$. Consequently, the construction $s \mapsto f_ s(s)$ determines a function $f: S_0 \rightarrow T$, which is an isomorphism of $S_0$ with an initial segment $T_0 \subseteq T$. If $S_0 = S$, then $f$ is an initial segment embedding from $S$ to $T$. If $T_0 = T$, then $g = f^{-1}$ is an initial segment embedding from $T$ to $S$. Assume that neither of these conditions is satisfied: that is, the sets $S \setminus S_0$ and $T \setminus T_0$ are both nonempty. Let $s$ be a least element of $S \setminus S_0$, and let $t$ be a least element of $T \setminus T_0$. Then $f$ extends uniquely to an initial segment embedding

\[ f_{\leq s}: S_{\leq s} = S_0 \cup \{ s\} \xrightarrow {\sim } T_0 \cup \{ t\} \subseteq T \quad \quad s \mapsto t. \]

The existence of $f_{\leq s}$ shows that $s$ belongs to $S_0$, which is a contradiction. $\square$

Remark 5.4.1.18. In the situation of Corollary 5.4.1.17, suppose that conditions $(1)$ and $(2)$ are both satisfied: that is, there exist initial segment embeddings $f: S \hookrightarrow T$ and $g: T \hookrightarrow S$. Then $g \circ f$ is an initial segment embedding of $S$ into itself, and therefore coincides with $\operatorname{id}_{S}$ (Corollary 5.4.1.16). The same argument shows that $f \circ g = \operatorname{id}_{T}$, so that $f$ and $g$ are mutually inverse bijections. In particular, $S$ and $T$ have the same order type.

Definition 5.4.1.19. Let $\alpha $ and $\beta $ be ordinals, given by the order types of well-ordered sets $(S, \leq )$ and $(T, \leq )$. We write $\alpha \leq \beta $ if there exists an initial segment embedding from $(S, \leq )$ to $(T, \leq )$ (note that this condition depends only on the order types of $S$ and $T$).

Proof. The reflexivity of the relation $\leq $ follows from Example 5.4.1.12, and the transitivity follows from Remark 5.4.1.13. Let $\alpha $ and $\beta $ be ordinals, which we identify with the order types of well-ordered sets $(S, \leq )$ and $(T, \leq )$, respectively. Invoking Corollary 5.4.1.17, we deduce that $\alpha \leq \beta $ or $\beta \leq \alpha $. Moreover, if both conditions are satisfied, then Remark 5.4.1.18 shows that $\alpha = \beta $. $\square$

Remark 5.4.1.21. Let $(S,\leq )$ and $(T, \leq )$ be well-ordered sets. The following conditions are equivalent:

$(1)$

There exists an initial segment embedding $f: S \hookrightarrow T$.

$(2)$

There exists a strictly increasing function $f: S \hookrightarrow T$.

The implication $(1) \Rightarrow (2)$ is immediate from the definitions. To prove the converse, let $f: S \hookrightarrow T$ be a strictly increasing function, and suppose that there is no initial segment embedding from $S$ to $T$. Invoking Corollary 5.4.1.17, we deduce that there is an initial segment embedding $g: T \hookrightarrow S$. The composition $(g \circ f): S \hookrightarrow S$ is strictly increasing, and therefore satisfies $(g \circ f)(s) \geq s$ for each $s \in S$ (Proposition 5.4.1.14). Since the image of $g$ is an initial segment $S_0 \subseteq S$, it follows that $S_0 = S$, so that $g^{-1}: S \xrightarrow {\sim } T$ is an isomorphism of linearly ordered sets.

We now show that, for every ordinal $\alpha $, there is a preferred candidate for a well-ordered set of order type $\alpha $: namely, the collection $\mathrm{Ord}_{< \alpha }$ of ordinals smaller than $\alpha $.

Proposition 5.4.1.22. Let $(S, \leq )$ be a well-ordered set, and let $\alpha $ denote its order type. Then there is a unique order-preserving bijection $S \rightarrow \mathrm{Ord}_{< \alpha }$, which carries each element $s \in S$ to the order type of the well-ordered set $S_{< s} = \{ s' \in S: s' < s \} $.

Proof. We will prove existence; uniqueness then follows from Corollary 5.4.1.16. For each $s \in S$, let $\alpha _{s}$ denote the order type of the set $S_{< s}$ (which is well-ordered, by virtue of Remark 5.4.1.5). Note that, since there is an initial segment embedding $S_{< s} \hookrightarrow S$ which is not bijective, we must have $\alpha _{s} < \alpha $ (Remark 5.4.1.18). Consequently, the construction $s \mapsto \alpha _{s}$ determines a function $S \rightarrow \mathrm{Ord}_{< \alpha }$. If $s < t$ in $S$, then there is an initial segment embedding from $S_{< s}$ to $S_{< t}$ which is not bijective, so that $\alpha _{s} < \alpha _{t}$ (again by Remark 5.4.1.18). To complete the proof, it will suffice to show that the function $s \mapsto \alpha _{s}$ is surjective. Let $\beta $ be an ordinal which is strictly smaller than $\alpha $. Then $\beta $ is the order type of some initial segment $S_0 \subsetneq S$. Since $S$ is well-ordered, the set $S \setminus S_0$ has a smallest element $s$. It follows that $S_0 = S_{< s}$, so that $\beta = \alpha _{s}$. $\square$

Corollary 5.4.1.23. For every ordinal $\alpha $, $\mathrm{Ord}_{< \alpha }$ is a well-ordered set of order type $\alpha $.

Corollary 5.4.1.24. Let $S$ be any nonempty collection of ordinals. Then $S$ has a least element.

Proof. Choose an ordinal $\alpha \in S$. If $\alpha $ is a least element of $S$, then we are done. Otherwise, we can replace $S$ by the nonempty subset $S_{< \alpha } = \{ \beta \in S: \beta < \alpha \} $. Note that $S_{< \alpha }$ is a nonempty subset $\mathrm{Ord}_{< \alpha }$, and therefore has a smallest element by virtue of Corollary 5.4.1.23. $\square$

Warning 5.4.1.25 (The Burali-Forti Paradox). One can informally summarize Corollary 5.4.1.24 by saying that the collection $\mathrm{Ord}$ of all ordinals is well-ordered (with respect to the order relation of Definition 5.4.1.19). Beware that one must treat this statement with some care to avoid paradoxes. The proof of Proposition 5.4.1.22 shows that the order type of $\mathrm{Ord}$ is strictly larger than $\alpha $, for each ordinal $\alpha \in \mathrm{Ord}$. This paradox has a standard remedy: we regard the collection $\mathrm{Ord}$ as “too large” to form a set (so that its order type is not regarded as an ordinal).

Definition 5.4.1.26. Let $(S, \leq )$ and $(T, \leq )$ be linearly ordered sets. We say that a function $f: S \rightarrow T$ is cofinal if it is nondecreasing and, for every element $t \in T$, there exists an element $s \in S$ satisfying $f(s) \geq t$.

Proposition 5.4.1.27. Let $(T, \leq )$ be a linearly ordered set. There exists a well-ordered subset $S \subseteq T$ for which the inclusion map $S \hookrightarrow T$ is cofinal.

Proof. Let $\{ S_ q \} _{q \in Q}$ be the collection of all well-ordered subsets of $T$. We regard $Q$ as a partially ordered set, where $q \leq q'$ if the set $S_{q}$ is an initial segment of $S_{q'}$. This partial ordering satisfies the hypotheses of Zorn's lemma, and therefore contains a maximal element $S_{\mathrm{max}}$. To complete the proof, it will suffice to show that the inclusion $S_{ \mathrm{max}} \hookrightarrow T$ is cofinal. Assume otherwise: then there exists an element $t \in T$ satisfying $s < t$ for each $s \in S_{\mathrm{max}}$. Then $S_{\mathrm{max}}$ is an initial segment of the well-ordered subset $S_{\mathrm{max}} \cup \{ t \} \subseteq T$, contradicting the maximality of $S_{\mathrm{max}}$. $\square$

Definition 5.4.1.28 (Cofinality). Let $(T, \leq )$ be a linearly ordered set. We let $\mathrm{cf}(T)$ denote the smallest ordinal $\alpha $ for which there exists a well-ordered set $(S, \leq )$ of order type $\alpha $ and a cofinal function $f: S \rightarrow T$. We refer to $\mathrm{cf}(T)$ as the cofinality of the linearly ordered set $T$.

If $\beta $ is an ordinal, let $\mathrm{cf}(\beta )$ denote the cofinality $\mathrm{cf}(T)$, where $(T, \leq )$ is any well-ordered set of order type $\beta $. We refer to $\mathrm{cf}(\beta )$ as the cofinality of $\beta $.

Remark 5.4.1.29. For any linearly ordered set $(T, \leq )$, the identity map $\operatorname{id}: T \rightarrow T$ is cofinal. Consequently, if $T$ is well-ordered set of order type $\alpha $, then we have $\mathrm{cf}(\alpha ) = \mathrm{cf}(T) \leq \alpha $. Beware that the inequality is often strict.

Example 5.4.1.30. Let $(T, \leq )$ be a linearly ordered set. Then $\mathrm{cf}(T) = 0$ if and only if $T$ is empty.

Example 5.4.1.31. Let $(T, \leq )$ be a nonempty linearly ordered set. The following conditions are equivalent:

  • The cofinality $\mathrm{cf}(T)$ is a positive integer.

  • The cofinality $\mathrm{cf}(T)$ is equal to $1$.

  • The linearly ordered set $T$ contains a largest element.

Example 5.4.1.32. Let $(T, \leq )$ be a linearly ordered sets. Then the cofinality $\mathrm{cf}(T)$ is equal to $\omega $ if and only if $T$ contains an unbounded increasing sequence $\{ t_0 < t_1 < t_2 < \cdots \} $.

Proposition 5.4.1.33. Let $(T, \leq )$ be a linearly ordered set. Then the cofinality $\mathrm{cf}(T)$ is the smallest ordinal with the following property:

$(\ast )$

There exists a well-ordered set $(S, \leq )$ of order type $\alpha $ and a function $f: S \rightarrow T$ which is unbounded (that is, every element $t \in T$ satisfies $t \leq f(s)$ for some $s \in S$). Here we do not require $f$ to be nondecreasing.

Proof. It is clear that the cofinality $\mathrm{cf}(T)$ satisfies condition $(\ast )$. For the converse, assume that $(S, \leq )$ is a well-ordered set of order type $\alpha $ and that $f: S \rightarrow T$ is an unbounded function. Let us say that an element $s \in S$ is good if, for every element $s' < s$ of $S$, we have $f(s') < f(s)$. Let $S_0$ be the collection of good elements of $S$, and set $f_0 = f|_{ S_0 }$. By construction, the function $f_0$ is strictly increasing. Moreover, the order type of $S_0$ is $\leq \alpha $ (Remark 5.4.1.21). To complete the proof, it will suffice to show that $f_0: S_0 \hookrightarrow T$ is cofinal. Fix an element $t \in T$, and set $S_{\geq t} = \{ s \in S: t \leq f(s) \} $. We wish to show that the intersection $S_{\geq t} \cap S_0$ is nonempty. We first observe that $S_{\geq t}$ is nonempty (by virtue of our assumption that $f$ is unbounded). Since $(S, \leq )$ is well-ordered, the set $S_{\geq t}$ contains a least element $s$. We claim that $s$ belongs to $S_0$. Assume otherwise: then there exists some $s' < s$ satisfying $f(s') \geq f(s)$. It follows that $s'$ belongs to $S_{\geq t}$, contradicting the minimality of $s$. $\square$

We conclude this section by observing that well-orderings exist in abundance.

By virtue of Example 5.4.1.4, Theorem 5.4.1.34 is a special case of the following more refined result:

Proposition 5.4.1.35. Let $(S, \preceq )$ be a well-founded partially ordered set. Then there exists a well-ordering $\leq $ on $S$ which refines $\preceq $ in the following sense: for every pair of elements $s,t \in S$ satisfying $s \preceq t$, we also have $s \leq t$.

Proof. Let $Q$ denote the set of ordered pairs $(T, \leq _{T})$, where $T$ is a subset of $S$ which is closed downward with respect to $\preceq $ and $\leq _{T}$ is a well-ordering of $T$ which refines $\preceq $. We regard $Q$ as a partially ordered set, where $(T, \leq _{T} ) \leq (T', \leq _{T'} )$ if $T$ is an initial segment of $T'$ (with respect to the ordering $\leq _{T'}$), and the ordering $\leq _{T}$ coincides with the restriction of $\leq _{T'}$. The partially ordered set $Q$ satisfies the hypotheses of Zorn's lemma, and therefore contains a maximal element $( T_{\mathrm{max}}, \leq _{ T_{\mathrm{max}} } )$. To complete the proof, it will suffice to show that $T_{\mathrm{max}} = S$. Suppose otherwise. Then the set $S \setminus T_{\mathrm{max}}$ is nonempty, and therefore contains an element $s$ which is minimal with respect to the ordering $\preceq $. Set $T' = T_{\mathrm{max}} \cup \{ s\} $, and extend $\leq _{ T_{\mathrm{max}} }$ to a linear ordering $\leq _{T'}$ of $T'$ by declaring $s$ to be a largest element. Then $(T', \leq _{T'} )$ is an element of $Q$, contradicting the maximality of the pair $( T_{\mathrm{max}}, \leq _{ T_{\mathrm{max}} } )$. $\square$