# Ordinal Numbers

**Ordinal numbers** (a.k.a. **ordinals**) generalize the notion of "labels" of objects in an ordered set. The collection of ordinals can be thought of as a "universal label collection," in the sense that any well-behaved order on a set is describable using a sequence of ordinals.

## Motivation

For example, the natural numbers \(\mathbb{N}\) have a standard ordering, which is expressed by the sequence of labels \(\{1, 2, 3, \cdots\}\). The integers double as both elements of \(\mathbb{N}\) and as labels for the order on \(\mathbb{N}\); following the latter sense, one thinks of \(\{1, 2, 3, \cdots\}\) as the *finite* ordinals. This is because any order on any finite set \(S\), say of size \(n\), can be described by a bijection \(f: \{1, 2, \cdots, n\} \to S\); the bijection induces the order \(\le_{S}\) on \(S\) given by \(a\le_{S} b\) iff \(f^{-1} (a) \le f^{-1} (b)\).

Similarly, any order on \(\mathbb{N}\) can be described using only finite ordinals. However, if an infinite set \(S\) has larger cardinality than \(\mathbb{N}\), the labels \(\{1, 2, 3, \cdots\}\) would not suffice to describe the entire order on \(S\). Accordingly, one introduces the *infinite* ordinal \(\omega\), which is constructed to be larger than any finite ordinal. Then, an element of \(S\) which is larger in the ordering \(\le_{S}\) than any of the elements labeled by \(\{1, 2, 3, \cdots\}\) could be labeled with \(\omega\).

## Preliminaries: Ordering Sets

Let \(S\) be a set. A **total order** on \(S\) is a binary relation, denoted by \(\le \), such that for all \(a, b, c \in S\), the following axioms hold:

- Either \(a\le b\) or \(b \le a\).
- If \(a\le b \) and \(b\le a\), then \(a=b\).
- If \(a\le b\) and \(b\le c\), then \(a\le c\).

For example, the standard ordering on \(\mathbb{R}\) is a total order. As a consequence, the *dictionary order* on \(\mathbb{R}^n\) is also a total order; this is defined by setting \[(x_1, x_2, \cdots, x_n) \le (y_1, y_2, \cdots, y_n)\] iff \(x_i \le y_i\) in the standard ordering on \(\mathbb{R}\) for all \(1\le i \le n\).

A total order \(\le \) on \(S\) is called a **well order** if it permits no infinite decreasing sequence of elements in \(S\). Equivalently, \(\le \) is a well order iff every non-empty subset of \(S\) has a least element in the order \(\le\). Note that \(\mathbb{R}\) with the standard ordering is *not* well-ordered, since for every element \(x\in \mathbb{R}\), the element \(y:= x-1 \in \mathbb{R}\) satisfies \(y \le x\). However, the natural numbers \(\mathbb{N}\) with their natural ordering are well-ordered, by the well-ordering principle.

Two sets \(A\) and \(B\), with total orders \(\le_{A}\) and \(\le_{B}\) respectively, are called **order-isomorphic** if there exists a bijection \(f: A \to B\) such that \(a \le_{A} b\) implies \(f(a) \le_{B} f(b)\) for all \(a,b \in A\).

Let \(A\) be the number of totally-ordered sets below, and let \(B\) be the number of well-ordered sets below. What is \(A+B\)?

\(S = \mathbb{R}\) with the standard order.

\(S = 2^{\mathbb{R}}\), the power set of \(\mathbb{R}\), ordered by set inclusion, i.e. \(A \le B\) iff \(A \subseteq B\).

\(S = \mathbb{R}^2\) with the dictionary order.

\(S = \mathbb{N}\), with the order given by \[3, 5, 7, \cdots, 3 \cdot 2, 5 \cdot 2, 7\cdot 2, \cdots, \] \[3 \cdot 2^2, 5 \cdot 2^2, 7 \cdot 2^2, \cdots, 3\cdot 2^3, \cdots, 2^3, 2^2, 2^1, 2^0\] where \(a\le b\) if \(a\) appears before \(b\) in the sequence or \(a = b\).

## Constructing Ordinal Numbers

Suppose that a sequence of ordinal labels has been constructed. Then, every ordinal \(x\) describes a well-ordered set, namely the set of all ordinals less than \(x\). This set, which we also denote by \(x\), can be thought of as the canonical example of a particular well-ordered set, in the sense that it represents the equivalence class of all well-ordered sets that are order-isomorphic to it.

To illustrate this, consider the finite ordinal \(5\), which one identifies with the ordered set of ordinals less than it, namely \(5 = \{1, 2, 3, 4\}\). Then, any well-ordered four element set is order-isomorphic to \(5\); for example, the four element set \(\{a,b,c,d\}\) with well order \(b\le a \le d\le c\) permits the order-isomorphism \(f: 5 \to \{a,b,c,d\}\) given by \(f(1) = b\), \(f(2) = a\), \(f(3) = d\), and \(f(4) = c\).

Based on this intuition, one formally defines ordinals as equivalence classes of well-ordered sets. If \((A, \le _{A})\) and \((B, \le_{B})\) are well-ordered sets, then one writes \(A \sim B\) if \(A\) and \(B\) are order-isomorphic; this relation \(\sim\) is an equivalence relation, and the equivalence classes obtained are called **ordinals**. Denote by \([A]\) the equivalence class of \(A\), i.e. the ordinal containing the well-ordered set \(A\).

In this formalism, the finite ordinals are precisely \(1:= [\emptyset], 2:= [\{1\}], 3:= [\{1, 2\}], 4:=[\{1,2,3\}], \cdots\). The smallest infinite ordinal is \(\omega := [\mathbb{N}]\). For an example of an infinite ordinal larger than \(\omega\), consider the set \(S:= \mathbb{N} \cup \{\star\}\) with well order \[1 \le 2 \le 3 \le \cdots \le \star.\] Since \(S\) does not have the same cardinality as \(\mathbb{N}\), the ordinal \([S]\) does not equal \(\omega\). Usually, one denotes \(\omega + 1 := [S]\).