Well-Orderings and Ordinal Numbers

Ordinal numbers generalize the concept of "position in a sequence" to infinite well-ordered sets, providing canonical representatives for each order type.

Well-Ordered Sets

Definition4.1Well-ordering

A well-ordering on a set $A$ is a total order $\leq$ such that every nonempty subset of $A$ has a least element. The pair $(A, \leq)$ is called a well-ordered set. Equivalently, there are no infinite strictly decreasing sequences $a_0 > a_1 > a_2 > \cdots$ in $A$ .

ExampleExamples and non-examples

$(\mathbb{N}, \leq)$ is well-ordered.
$(\{0, 1, 2, \ldots, \omega\}, \leq)$ where $\omega$ is "after all naturals" is well-ordered.
$(\mathbb{Z}, \leq)$ is not well-ordered: $\mathbb{Z}^-$ has no least element.
$(\mathbb{Q} \cap [0,1], \leq)$ is not well-ordered: $\{1/n : n \geq 1\}$ has no least element.
Any finite totally ordered set is well-ordered.

Von Neumann Ordinals

Definition4.2Ordinal number (von Neumann)

A set $\alpha$ is an ordinal if:

$\alpha$ is transitive: $x \in y \in \alpha \implies x \in \alpha$ .
$\alpha$ is well-ordered by $\in$ .

The class of all ordinals is denoted $\mathbf{Ord}$ . The first few ordinals are:

$0 = \emptyset, \quad 1 = \{0\} = \{\emptyset\}, \quad 2 = \{0,1\}, \quad 3 = \{0,1,2\}, \quad \ldots$

Each ordinal $\alpha$ equals the set of all ordinals less than $\alpha$ : $\alpha = \{\beta : \beta < \alpha\}$ .

Definition4.3Successor and limit ordinals

An ordinal $\alpha$ is a successor ordinal if $\alpha = \beta + 1 := \beta \cup \{\beta\}$ for some ordinal $\beta$ . An ordinal $\alpha > 0$ is a limit ordinal if it is not a successor, i.e., $\alpha = \sup\{\beta : \beta < \alpha\}$ with no maximum. The first limit ordinal is:

$\omega = \{0, 1, 2, 3, \ldots\} = \mathbb{N}.$

The Ordinal Hierarchy

RemarkOrdinals beyond omega

After $\omega$ , ordinals continue:

$\omega, \omega+1, \omega+2, \ldots, \omega \cdot 2, \omega \cdot 2 + 1, \ldots, \omega \cdot 3, \ldots, \omega^2, \ldots, \omega^\omega, \ldots, \omega^{\omega^\omega}, \ldots, \varepsilon_0, \ldots$

where $\varepsilon_0$ is the first ordinal satisfying $\omega^{\varepsilon_0} = \varepsilon_0$ . Every countable ordinal is still countable (as a set), but the "positions" extend far beyond $\mathbb{N}$ . The first uncountable ordinal is $\omega_1$ .

Theorem4.1Trichotomy for ordinals

For any ordinals $\alpha, \beta$ , exactly one holds: $\alpha \in \beta$ (i.e., $\alpha < \beta$ ), $\alpha = \beta$ , or $\beta \in \alpha$ (i.e., $\beta < \alpha$ ). Moreover, every set of ordinals is well-ordered by $\in$ .

ExampleNon-commutativity of ordinal addition

Ordinal addition is not commutative: $1 + \omega = \omega \neq \omega + 1$ . This is because $1 + \omega$ places one element before $\omega$ -many elements, giving an order isomorphic to $\omega$ . But $\omega + 1$ places one element after $\omega$ -many elements, giving a new order type.