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. This is in contrast to the cardinals, which only describe cardinality, and which are applicable to non-well-ordered sets.

The idea of ordinals as a transfinite extension of the counting numbers was first invented by Georg Cantor in the 19th century.

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.

One is able to define ordinals without this recursive definition. In particular, in ZFC, the two following statements are equivalent to \(\alpha\) being an ordinal.

• \(\alpha\) is a transitive set and all elements of \(\alpha\) are transitive.
• \(\alpha\) is a transitive set and the \(\in\) relation restricted to \(\alpha\) is a strict well-order.

Using supertasks, it is possible to count up to any given countable ordinal in a finite amount of time. For example, to count to \(\omega\), one takes 30 seconds to count from 0 to 1, 15 seconds to count from 1 to 2, 7.5 seconds to count from 2 to 3, 3.75 seconds to count from 3 to 4, and so on. After a minute, all numbers \(< \omega\) will be exhausted. In general, one can count to \(\omega \cdots n\) in \(n\) seconds. By iterating this process another layer, one can count to \(\omega^2\): one takes 1 minute to count from 0 to \(\omega\), 30 seconds to count from \(\omega\) to \(\omega 2\) (so 15 seconds to count from \(\omega\) to \(\omega + 1\), 7.5 seconds to count from \(\omega + 1\) to \(\omega + 2\), and so on), then 15 seconds to count from \(\omega 2\) to \(\omega 3\), and so on. In general, any countable ordinal can be counted to in a finite amount of time. However, it is impossible to count to \(\omega_1\) in any finite amount of time. This idea is closely related to matchstick diagrams - it is possible to draw a diagram for an arbitrary countable ordinal but not \(\omega_1\).

The order type of a well-ordered set is intuitively its "length". Alternatively, one may think of the order type of a set \(X\) as the smallest ordinal so that the ordinals below are sufficient to number the elements of \(X\), while preserving the order. For example, the order type of a singleton if 1, since pairing 0 with the single element of that set is a bijection and preserves order, therefore, the ordinals below 1 are sufficient to order-preservingly number the elements of the singleton. For finite sets, the order type and cardinality are equal.

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\}\)

Ordinal arithmetic is well-defined by the axioms of union, pairing and replacement.

There are helpful visual representations for these, namely with matchstick diagrams. For example, \(\alpha + \beta\) can be visualized as (a diagram for) \(\alpha\), followed by a copy of (a diagram for) \(\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, and they therefore have not only the same cardinality but the same order type. 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.

Note that, generally, if one of \(\alpha\) and \(\beta\) is infinite, then \(\alpha + \beta\) will have the same cardinality as \(\max(\alpha, \beta)\), but, as we mentioned, not necessarily the same order type. A similar result holds for ordinal multiplication and addition, and it can be shown by "interlacing" well-ordered sets with the respective order types. An exercise is to formally find a bijection from \(\max(\alpha, \beta)\) to \(\alpha + \beta\), assuming the former is infinite.

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.