Ordinal

In set theory, the ordinal numbers or ordinals are an extension of the natural numbers that describe the order types of well-ordered sets. A set \( S \) is well-ordered if each non-empty \( T \subseteq S \) has a least element. For example, any finite set of real numbers is well-ordered, as well as the set of natural numbers, while neither the set of nonnegative rationals nor the set of integers is well-ordered.

Von Neumann definition

In a pure set theory such as ZFC, we need a way to define ordinals as objects of study. The Von Neumann definition of ordinals does this, by associating each ordinal \( \alpha \) is defined as the set of all ordinals less than \( \alpha \). In particular:

• \(0 := \{\}\)
• \(\alpha+1 := \alpha \cup \{\alpha\}\)
• If \(X\) is a set of ordinals, then \(\bigcup X\)

By associating the natural number \(0\) with the ordinal \(0\), \(1\) with \(0+1 = \{0\}\), \(2\) with \(0+1+1 = \{0,1\}\), and so on, the natural numbers can be embedded inside the ordinals. However, the set of natural numbers (which is its own union) is also an ordinal, and commonly written as \(\omega\). One convenient property of this definition of ordinals is that \(\alpha < \beta\) can be easily defined to mean \(\alpha \in \beta\), and thus \(\omega\) is an ordinal bigger than all the natural numbers. By continuing on this way, we can form a never-ending ladder of ordinals, and assign an order-type to any well-ordered set.

The order-type of a well-ordered set is intuitively its "length". In particular, the order-type of (the von Neumann representation) any natural number \(n\) is defined as \(n\). In general, any ordinal is its own order-type. But also many non-ordinal objects have order types. For example, say we were to reorder the natural numbers by putting all the even numbers first, followed by the odd numbers. This is still well-ordered, and has order-type \(\bigcup\{\omega+n: n < \omega\}\), also written \(\omega \cdot 2\).

Ordinal arithmetic

We can do arithmetic with ordinals like so:

• \(\alpha + 0 = \alpha\)
• \(\alpha + (\beta + 1) = (\alpha + \beta) + 1\)
• If \(\beta\) is not \(0\) or a successor to another ordinal (in which case it is called a limit ordinal), \(\alpha + \beta = \bigcup\{\alpha+\gamma: \gamma < \beta\}\)

One can see that this agrees with the usual definition of arithmetic for the natural numbers when \(\alpha\) and \(\beta\) are finite. Similarly:

• \(\alpha \cdot 0 = 0\)
• \(\alpha \cdot (\beta + 1) = (\alpha \cdot \beta) + \alpha\)
• If \(\beta\) is a limit ordinal, \(\alpha \cdot \beta = \bigcup\{\alpha \cdot \gamma: \gamma < \beta\}\)

Again, this agrees with the usual definition. Lastly:

• \(\alpha^0 = 1\)
• \(\alpha^{\beta+1} = \alpha^\beta \cdot \alpha\)
• If \(\beta\) is a limit ordinal, \(\alpha^\beta = \bigcup\{\alpha^\gamma: \gamma < \beta\}\)

There are helpful visual representations for these, namely with sets of lines. For some basic intuition, see this video. For example, \(\alpha + \beta\) can be visualized as \(\alpha\), followed by a copy of \(\beta\). Note that our definition gives \(1 + \omega = \bigcup\{1+n: n < \omega\} = \omega\), and this makes sense, since a single line, followed by infinitely many lines, is no more than just infinitely many lines. Meanwhile, \(\omega + 1 = \omega \cup \{\omega\}\): you have infinitely many lines, followed by a single one after all of them. This intuition is formalized by the following statement, which is provable over ZFC: "if \(X\) and \(Y\) are well-ordered sets with order-types \(\alpha\), \(\beta\), respectively, then \(X\), concatenated with a copy of \(Y\), has order-type \(\alpha + \beta\)".

For ordinal multiplication, \(\alpha \cdot \beta\) can be imagined as \(\beta\), with each individual line in \(\beta\) replaced with a copy of \(\alpha\). For example, \(\omega \cdot 2\), is two lines, with each individual line replaced with a copy of \(\omega\), i.e: 2 copies of \(\omega\), or \(\omega + \omega\). \(\alpha^\beta\) may be described in terms of functions \(f:\beta\to\alpha\) with finite support.

Equivalence class definition

Another common definition of ordinals, often used in settings not based on set theory, is as equivalence classes of well-orders. Namely, we say that two well-ordered sets are order-isomorphic (iso- for "same" and morphic for "form" or "shape") if there is a way of relabelling the elements of the first set into elements of the second set, so that the order is preserved. Note that this implies the two sets have the same size, but is a strictly stronger notion: the video linked in the previous section shows that \(\omega\) and \(\omega + 1\) have the same size, yet aren't order-isomorphic. Order-isomorphism is used to give the definition of order-type: the order-type of \(X\) is the unique ordinal \(\alpha\) which it is order-isomorphic to. However, outside of this context, it is used to give an alternate, simpler (yet formally more troublesome) definition of ordinals. Namely, an ordinal can be defined as the equivalence class of sets under order-isomorphism. For example, \(\omega\) is defined as the class of all sets which are order-isomorphic to the natural numbers. The issue is that all ordinals, other than zero, are now proper classes, which makes formal treatment more difficult.