Ordinal Numbers

Home → Ordinal Numbers

An ordinal number (or ordinal) is a number that indicates position or order of objects, such as first, second, third, and so on.

There are several approaches to define ordinal numbers, some of which are considered below.

Ordinals as an Extension of the Natural Numbers

Loosely speaking, ordinal numbers can be considered as an extension of the natural numbers into infinite values. We assume here that the set of natural numbers \(\mathbb{N}\) includes zero. So the finite ordinals are the natural numbers \(0,1,2,3,4,5,\ldots.\) The least infinite (or the first transfinite) ordinal is denoted by \(\omega,\) which also coincides with the cardinal number \(\aleph_0.\) Next, we continue with the ordinals \(\omega+1,\) \(\omega+2,\) \(\omega+3,\ldots.\) After that come \(\omega \cdot 2,\) \(\omega \cdot 2 + 1,\) \(\omega \cdot 2 + 2,\ldots\) and so on until we reach \(\omega \cdot \omega = \omega^2,\) followed by \(\omega^3,\) \(\omega^4,\ldots,\) \(\omega^{\omega},\) \(\omega^{\omega+1},\ldots,\) \(\omega^{\omega^{\omega}},\) \(\omega^{\omega^{\omega^{\omega}}},\) \(\omega^{\omega^{\omega^{\cdot^{\cdot^{\omega}}}}}, \ldots\) The process can be continued indefinitely.

The smallest uncountable ordinal number is denoted by \(\omega_1.\)

Ordinals as Equivalence Classes

Ordinal numbers are used to describe ordering in well ordered sets. Recall that two well-ordered sets \(A\) and \(B\) are order-isomorphic (denoted \(A \cong B\)) if there is a function \(f: A \to B\) such that, for every \(x,y \in A,\)

\[x\;{ \le _A}\;y\;\; \Rightarrow f\left( x \right){ \le _B}\,f\left( y \right).\]

The function \(f\) here is an order-preserving bijection, that is, order isomorphism preserves well-ordering.

It is easy to show that the relation of "being order-isomorphic" is reflexive, transitive, and symmetric. Hence, the relation \(\cong\) between sets is an equivalence relation. It partitions all well-ordered sets into equivalence classes, which are called order types.

Each order type is represented by a distinct ordinal. It can be shown that all well-ordered sets of cardinality \(n\) have the same order type, which is represented by the ordinal \(n.\) Thus, we obtain the ordinals \(0,1,2,3,4,5,\ldots.\)

Unfortunately, the definition based on equivalence classes fails in axiomatic set theories (\(\text{ZF}, \text{ZFC},\) and others) because equivalence classes do not form a set. However, for each equivalence class, we can choose a set that represents the class. This particular well-ordered set is considered to be an ordinal. This approach is used in the von Neumann definition of ordinals.

Von Neumann Definition of Ordinals

Using von Neumann's construction, every ordinal is defined as the well-ordered set of all smaller ordinals. Formally, if \(\alpha\) and \(\beta\) denote ordinals, then an ordinal \(\alpha\) is given by

\[\alpha = \left\{ {\beta \mid \beta \lt \alpha } \right\},\]

where the relation \(\lt\) between the ordinals implies set membership, that is, \(\beta \lt \alpha\) if \(\beta \in \alpha.\)

Since any ordinal is a well-ordered set, it has the minimum element, which is equal to \(0.\) An ordinal may or may not have a maximum element. For example, the ordinal \(\omega\) representing all natural numbers does not have a maximum, while the ordinal \(\omega + 3\) has the maximum \(\omega + 2:\)

\[\omega + 3 = \left\{ {0,1,2, \ldots ,\omega,\omega + 1,\omega + 2} \right\}.\]

If an ordinal \(\alpha\) has a maximum, the next ordinal after it is called a successor ordinal and is written as \(\alpha + 1\) or \(\alpha^{+}.\) A nonzero ordinal that is not a successor is called a limit ordinal. For example, in the sequence

\[{0,1,2, \ldots ,\omega,\omega + 1,\omega + 2},\]

the number \(\omega\) is a limit ordinal.

Most ordinals are successors. The successor to an ordinal is defined as

\[\alpha + 1 = \alpha \cup \left\{ \alpha \right\}.\]

Note the distinction between \(\alpha\) and \(\left\{ \alpha \right\}.\) Here \(\alpha\) denotes an ordinal, but \(\left\{ \alpha \right\}\) is a set containing a single ordinal \(\alpha.\)

The least finite ordinal is

\[0 = \varnothing = \left\{ \right\} .\]

The next ordinal \(1\) is given by

\[1 =\varnothing \cup \left\{ \varnothing \right\} = \left\{ \varnothing \right\}.\]

Continuing this pattern, we obtain

\[2 = 1 \cup \left\{ 1 \right\} = \left\{ \varnothing \right\} \cup \left\{ {\left\{ \varnothing \right\}} \right\} = \left\{ {\varnothing,\left\{ \varnothing \right\}} \right\},\]

\[3 = 2 \cup \left\{ 2 \right\} = \left\{ {\varnothing,\left\{ \varnothing \right\}} \right\} \cup \left\{ {\left\{ {\varnothing,\left\{ \varnothing \right\}} \right\}} \right\} = \left\{ {\varnothing,\left\{ \varnothing \right\},\left\{ {\varnothing,\left\{ \varnothing \right\}} \right\}} \right\},\]

and so on. It is clear that the ordinal \(n+1\) in the von Neumann construction is the set containing all previous ordinal numbers \(0,1,2,\ldots, n.\)

Ordinal Arithmetic

Ordinals represent a specific type of numbers. Similarly to other numbers, we can perform operations on ordinals. We consider three basic operations: addition, multiplication, and exponentiation. The Greek letters \(\alpha, \beta, \gamma, \delta\) below denote ordinals.

Ordinal Addition

The addition operation can be defined by induction on \(\beta:\)

\(\alpha + 0 = \alpha .\)
\(\alpha + \left( {\beta + 1} \right) = \left( {\alpha + \beta } \right) + 1,\) where \(\text{"}+1\text{"}\) denotes the successor ordinal.
If \(\beta\) is a limit ordinal, then \(\alpha + \beta = \sup \left\{ {\alpha + \delta \mid \delta \lt \beta } \right\}.\)

Example 1

Determine \(\omega +2.\) Here \(\alpha = \omega,\) \(\beta = 2.\) The number \(\beta = 2\) is the successor to \(1\). Then

\[\omega + 2 = \omega + \left( {1 + 1} \right) = \left( {\omega + 1} \right) + 1.\]

The successor ordinal of \(\omega + 1\) is \(\omega + 2.\) Hence,

\[\omega + 2 = \left( {\omega + 1} \right) + 1 = \omega + 2.\]

Example 2

Calculate \(2+\omega.\) We have here \(\alpha = 2,\) \(\beta = \omega.\) Note that \(\beta = \omega\) is a limit ordinal. Therefore,

\[2 + \omega =\sup{\left\{ {2 + \delta \mid \delta \lt \omega} \right\} } = 2,3,4, \ldots = \omega.\]

So ordinal addition is not commutative:

\[1 + \omega = \omega \ne \omega + 1.\]

Ordinal addition is associative:

\[\left( {\alpha + \beta } \right) + \gamma = \alpha + \left( {\beta + \gamma } \right).\]

Ordinal Multiplication

The multiplication operation can be introduced by induction on \(\beta:\)

\(\alpha \cdot 0 = 0.\)
\(\alpha \cdot \left( {\beta + 1} \right) = \alpha \cdot \beta + \alpha,\) where \(\text{"}+1\text{"}\) denotes the successor ordinal.
If \(\beta\) is a limit ordinal, then \(\alpha \cdot \beta = \sup \left\{ {\alpha \cdot \delta \mid \delta \lt \beta } \right\}.\)

Examples

\[\begin{array}{*{20}{l}} {1 \cdot 1 = 1 \cdot \left( {0 + 1} \right) = 1 \cdot 0 + 1 = 0 + 1 = 1}\\[1em] {2 \cdot 1 = 2 \cdot \left( {0 + 1} \right) = 2 \cdot 0 + 2 = 0 + 2 = 2}\\[1em] {1 \cdot 2 = 1 \cdot \left( {1 + 1} \right) = 1 \cdot 1 + 1 = 1 + 1 = 2}\\[1em] {\omega \cdot 1 = \omega \cdot \left( {0 + 1} \right) = \omega \cdot 0 + \omega = 0 + \omega = \omega}\\[1em] {\omega \cdot 2 = \omega \cdot \left( {1 + 1} \right) = \omega \cdot 1 + \omega = \omega + \omega}\\[1em] {1 \cdot \omega = \sup{\left\{ {1 \cdot \delta \mid \delta \lt \omega} \right\} } = 0,1,2,3,\ldots = \omega}\\[1em] {2 \cdot \omega = \sup{\left\{ {2 \cdot \delta \mid \delta \lt \omega} \right\} } = 0,2,4,6,\ldots = \omega} \end{array}\]

Like addition, ordinal multiplication is not commutative:

\[2 \cdot \omega = \omega \ne \omega \cdot 2 = \omega + \omega.\]

Multiplication is associative:

\[\left( {\alpha \cdot \beta } \right) \cdot \gamma = \alpha \cdot \left( {\beta \cdot \gamma } \right).\]

Ordinal Exponentiation

The operation \(\alpha^{\beta}\) is also defined by induction:

\({\alpha ^0} = 1.\)
\({\alpha ^{\beta + 1}} = {\alpha ^\beta } \cdot \alpha,\) where \(\text{"}+1\text{"}\) denotes the successor ordinal.
If \(\beta\) is a limit ordinal, then \({\alpha ^\beta } = \sup \left\{ {{\alpha ^\delta } \mid \delta \lt \beta } \right\}.\)

Examples

\[\begin{array}{*{20}{l}} {{2^1} = {2^{0 + 1}} = {2^0} \cdot 2 = 1 \cdot 2 = 2}\\[1em] {{2^2} = {2^{1 + 1}} = {2^1} \cdot 2 = 2 \cdot 2 = 4}\\[1em] {{\omega^1} = {\omega^{0 + 1}} = {\omega^0} \cdot \omega = 1 \cdot \omega = \omega}\\[1em] {{\omega^2} = {\omega^{1 + 1}} = {\omega^1} \cdot \omega = \omega \cdot \omega}\\[1em] {{2^{\omega}} = \sup{\left\{ {2^\delta \mid \delta \lt \omega}\right\}} = 1,2,4,8, \ldots = \omega}\\ \end{array}\]

Some properties of ordinal exponentiation:

\({\alpha^1} = {\alpha}\)
\({1^{\alpha}} = {1}\)
\({\alpha ^{\beta + \gamma }} = {\alpha ^\beta } \cdot {\alpha ^\gamma }\)
\({\left( {{\alpha ^\beta }} \right)^\gamma } = {\alpha ^{\beta \,\cdot\, \gamma }}\)
If \(\alpha \lt \beta,\) then \({\alpha ^\gamma } \le {\beta ^\gamma }.\)
If \(\alpha \gt 1\) and \({\alpha ^\beta } = {\alpha ^\gamma },\) then \(\beta = \gamma.\)

Cantor Normal Form

Every ordinal number \(\alpha \gt 0\) can be uniquely represented in the form

\[\alpha = {\omega^{{\beta _1}}}{k_1} + {\omega^{{\beta _2}}}{k_2} + \ldots + {\omega^{{\beta _n}}}{k_n} = \sum\limits_{i = 1}^n {{w^{{\beta _i}}}{k_i}},\]

where \(n \ge 1,\) \({k_1},{k_2}, \ldots ,{k_n}\) are positive integers, and \(\alpha \gt {\beta _1} \gt {\beta _2} \gt \ldots \gt {\beta _n} \ge 0.\)

This decomposition is called the Cantor normal form of \(\alpha.\)