Ordinal Numbers

This image depicts the ordinals. It starts with the natural numbers 0, 1, 2, 3,... all the way to the $\omega$ ordinal, defined as larger than every integer, and then $\omega + 1, \omega + 2,$ etc. all the way to $\omega^\omega.$^[1]

Ordinal numbers have two related meanings. Colloquially, an ordinal number is a number that tells the position of something in a list, such as first, second, third, etc. This basic understanding extends to the meaning of ordinal numbers in set theory. In an ordered set, that is a collection of objects placed in some order, ordinal numbers (also called ordinals) are the labels for the positions of those ordered objects.

For example, the natural numbers $\mathbb{N}$ have a standard ordering, which is expressed by the sequence of labels $\{0,1, 2, 3, \ldots\}$. The integers double both as elements of $\mathbb{N}$ and as labels for the order on $\mathbb{N}$. This makes sense all the way up to infinite numbers. Ordinals are defined by the ordinals that come before. For instance, the ordinal $10$ can be identified as the set $\{0,1,2,3,4,5,6,7,8,9\}$.

The set of natural numbers is a countably infinite set. The "size" of the natural numbers as a countably infinite set is a common standard to categorize 2 types of infinite sizes: countable and uncountable. If elements of another set can be put into one-to-one correspondence with the natural numbers, that set also has a size of countably infinite.

The position of elements in finite sets are fairly obvious: they start with the natural numbers ${1, 2, 3, 4, ..., n}$, meaning $1^\text{st}, 2^\text{nd}, 3^\text{rd},$ and so on to $n^\text{th}.$ Note $0$ can be an ordinal, too. After the natural numbers is the first infinite ordinal $\omega$, and then $\omega+1, \omega+2, \omega +3$, etc. all the way to $\omega + \omega,$ or $\omega\cdot2$. Then $\omega\cdot2 + 1, \omega\cdot2 + 2$, etc. all the way to $\omega\cdot3$. Note, it's important to express this as $\omega + 1, \omega \cdot 2,$ or $\omega3,$ not $1+\omega , 2\cdot\omega,$ or $3\omega.$ Ordinals are not commutative, and $1+\omega$ would be treated the same as $1+\infty = \infty$, $1+\omega = \omega,$ whereas $\omega +1$ is an ordinal number decrementing one more than $\omega$.

This is beginning to form a pattern $\omega \cdot m+n,$ where $m$ and $n$ are natural numbers. This collection of ordinals is itself a set assigned the ordinal $\omega2$. There is also $\omega2, \omega3,...,\omega\omega,..., \omega\omega\omega,...$. And this can be continued indefinitely far. In fact, ordinals are designed to be continued indefinitely for there always to be another ordinal after the $...$.

Ordinals are linked to a unique kind of set called a well-ordered set. A well-ordered set is actually a type of totally-ordered set. A total-ordered set essentially means that given two elements, one will be smaller and one larger and that this distinction can be defined in a coherent manner. Formally, 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 ${0,1,2,3,4,5,6,...}$. As a consequence, the dictionary order, meaning the commonly understood order like ${a_1,a_2,a_3,...,a_k,...,b_1,b_2,...,b_k,...,c_k}$ on $\mathbb{R}^n$ is also a total order. This is defined by setting $$(x_1, x_2, \ldots, x_n) \le (y_1, y_2, \ldots, y_n)$$ iff $x_i \le y_i$ in the standard ordering on $\mathbb{R}$ for all $1\le i \le n$.

Back to well-ordered sets and ordinals! A well-ordered set is a total-ordered set with no infinite decreasing sequences. Ordinals may label the elements of the well-ordered set to measure the length of the whole set by the least ordinal that is not a label. 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$.

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 = \{0, 1, 2, 3, 4\}$. Then, any well-ordered four-element set (0 is the ordinal label for a non-element, for the zeroth element) 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\}], \ldots$. 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]$.

1. Pop-up Casket, . Omega-exp-omega-labeled. Retrieved January 24th, 2017, from https://commons.wikimedia.org/wiki/File:Omega-exp-omega-labeled.svg