Ordinal number

In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, nth, etc.) aimed to extend enumeration to infinite sets. Usually Greek letters are used for ordinal number variables to help distinguish them from natural number variables.

A finite set can be enumerated by successively labeling each element with the least natural number that has not been previously used. To extend this process to various infinite sets, ordinal numbers are defined more generally as a linearly ordered class of numbers that include the natural numbers and have the property that every non-empty collection (set or proper class) of ordinals has a least or "smallest" element (this is needed for giving a meaning to "the least unused element"). This more general definition allows us to define an ordinal number \(\omega\) (omega) to be the least element that is greater than every natural number, along with ordinal numbers ⁠\(\omega + 1\)⁠, ⁠\(\omega + 2\)⁠, etc., which are even greater than ⁠\(\omega\)⁠.

The Zermelo-Fraenkel set theory asserts that, for any set of ordinals, there exists another ordinal greater than all of them. The answer to the question "What if that set is the set of all ordinals?" (the Burali-Forti paradox) is that the collection of all ordinals is not a set, but a proper class.

A linear order such that every non-empty subset has a least element is called a well-order. The axiom of choice implies that every set can be well-ordered. Given two well-ordered sets, one is isomorphic to an initial segment of the other, and the isomorphism is unique. This allows a unique ordinal to be associated with each well-ordered set, known as its order type.

Ordinal numbers are distinct from cardinal numbers, which measure the size of sets. Although the distinction between ordinals and cardinals is not this apparent on finite sets (one can go from one to the other just by counting labels), they are very different in the infinite case, where different infinite ordinals can correspond to sets having the same cardinal. Like other kinds of numbers, ordinals can be added, multiplied, and exponentiated, although none of these operations are commutative.

Ordinals were introduced by Georg Cantor in 1883 to accommodate infinite sequences and classify derived sets, which he had previously introduced in 1872 while studying the uniqueness of trigonometric series.

A natural number (which, in this context, includes the number 0) can be used for two purposes: to describe the size of a set, or to describe the position of an element in a sequence. When generalized to infinite sets, the notion of size leads to cardinal numbers, and the notion of position leads to the ordinal numbers described here.

In a broader mathematical sense, counting can be viewed as the instantiation of mathematical induction. To enumerate a well-ordered set is effectively to verify a property for its elements sequentially. For the natural numbers, this is standard induction: if a property holds for 0, and its truth for ⁠\(n\)⁠ implies its truth for ⁠\(n+1\)⁠, then it holds for all natural numbers. This process corresponds to the first infinite ordinal, ⁠\(\omega\)⁠.

Mathematical contexts often require iterating beyond a single infinite limit. The ordinal ⁠\(\omega^2\)⁠ (represented in the figure) exemplifies the concept of nested induction. It consists of a sequence of distinct copies of the natural numbers ordered one after another. To verify a property for all ordinals less than ⁠\(\omega^2\)⁠, one performs an "inner" induction (counting through ⁠\(0, 1, 2, \dots\)⁠), establishes the limit at ⁠\(\omega\)⁠, and then proceeds to the next sequence (⁠\(\omega+1, \omega+2, \dots\)⁠). This structure parallels a nested loop in computer programming (e.g., iterating through pairs of natural numbers ⁠\((j, i)\)⁠ ordered lexicographically). Ordinals allow the definition of processes of arbitrary complexity, such as ⁠\(\omega^3\)⁠ (triple nesting) or ⁠\(\omega^\omega\)⁠ (induction over the depth of nested induction).

The validity of inductive counting rests on the property of well-foundedness, specifically the requirement that every process can be traced back to a "foundational" element. A linear order that exhibits this well-foundedness is termed a well-order. The existence of a "least" or minimal element in every non-empty subset of a well-ordered set grounds the principle of transfinite induction, generalizing standard induction by ensuring that if a property fails to hold, there exists a specific least counterexample.

Ordinals serve as the canonical abstractions of these well-ordered structures. A fundamental theorem in set theory establishes that any two well-ordered sets are comparable: given two well-orders, either they are isomorphic, or one is isomorphic to a proper initial segment of the other. This uniqueness implies that well-orders can be classified by their structure alone, independent of specific representations. Consequently, ordinal numbers are defined as the representative forms of these isomorphism classes.

A finite set can be enumerated by successively labeling each element with the least natural number that has not been previously used. To extend this process to various infinite sets, ordinal numbers are defined more generally as a linearly ordered class of numbers that include the natural numbers and have the property that every non-empty collection (set or proper class) of ordinals has a least or "smallest" element (this is needed for giving a meaning to "the least unused element"). This more general definition allows us to define an ordinal number \(\omega\) (omega) to be the least element that is greater than every natural number, along with ordinal numbers ⁠\(\omega + 1\)⁠, ⁠\(\omega + 2\)⁠, etc., which are even greater than ⁠\(\omega\)⁠.

The construction procedure of transfinite sequences implies that the ordinals used to label their elements are well-ordered. This means that:

Every non-empty collection of ordinals ⁠\(T\)⁠ has a unique least element.

Intuitively, the least ordinal in ⁠\(T\)⁠ is the "next" ordinal introduced after all ordinals strictly less than every ordinal in ⁠\(T\)⁠ have been used. In contrast, ⁠\(T\)⁠ need not have a greatest element, for example when ⁠\(T\)⁠ is the set of all natural numbers.

Being well-ordered is stronger than merely being linearly ordered. For example, the real numbers are naturally linearly ordered, but any open interval has no least element.

The importance of well-ordering is that it enables transfinite induction. If a statement ⁠\(P(\alpha)\)⁠ about an ordinal ⁠\(\alpha\)⁠ is not universally true for all ⁠\(\alpha\)⁠, i.e., if it has any counterexamples, then it must have a least counterexample. Conversely, if it can be proven that ⁠\(P(\alpha)\)⁠ is true whenever ⁠\(P(\beta)\)⁠ is true for all ⁠\(\beta < \alpha\)⁠, then it cannot have any least counterexample, and thus it cannot have any counterexample at all, i.e., it is indeed universally true.

In the usual Zermelo-Fraenkel (ZF) formalization of set theory, a well-ordered set is a totally ordered set ⁠\((S, \le)\)⁠ such that every non-empty subset ⁠\(T \subseteq S\)⁠ has a least element. Here “set” means a collection that is itself an object of ZF, as opposed to a proper class.

A well-ordered set can be written as a transfinite sequence by assigning ordinal labels to its elements in a way that respects ordering: ⁠\(a_\alpha \le a_\beta\)⁠ if and only if ⁠\(\alpha \le \beta\)⁠. (Such a one-to-one correspondence between two ordered sets is called an order isomorphism.) The labels used in such an enumeration form an initial segment of the ordinals, in the sense that if a label is used then every smaller ordinal label is also used. By well-orderedness, there is a unique least ordinal that is not used as a label; this ordinal determines the "length" of the sequence, and is called the order type of the well-ordering. Thanks to 0-based indexing, the order type coincides with the cardinality for finite sets, including the empty set. However, for infinite sets, different well-order relations ⁠\(\le\)⁠ can have different order types.

Order types can be defined without a preexisting notion of ordinals, by working directly with order isomorphisms between general well-ordered sets, just as cardinality can be defined through bijections between general (unordered) sets. As with bijections, being order-isomorphic is an equivalence relation on well-ordered sets; its equivalence classes correspond to order types (ordinals).

In the Principia Mathematica approach, the order type of a well-ordered set ⁠\((S, \le)\)⁠ is identified with its isomorphism class, i.e., the set of all well-ordered sets ⁠\((S', \le')\)⁠ order-isomorphic to ⁠\((S, \le)\)⁠. Since elements of ⁠\(S'\)⁠ are allowed to be anything, this definition has the “set of all sets” flavor, and in ZF such collections are generally too large to be sets. This definition can still be used in type theory and in Quine's axiomatic set theory New Foundations and related systems.

In ZF and related systems of axiomatic set theory, these equivalence classes are generally too large to form sets. Consequently, it is necessary to select a unique, canonical representative from each class, a single set that embodies the structure of the well-ordering. Since the fundamental relation in set theory is set membership (⁠\(\in\)⁠), the ideal representation is one where the abstract order relation ⁠\(<\)⁠ is translated directly into the membership relation ⁠\(\in\)⁠.

The von Neumann representation provides this canonical form. It relies on the observation that any well-founded relation satisfying certain properties can be mapped to a specific set where the relation becomes set membership. This mapping is known as the Mostowski collapse lemma.

When applied to a well-ordering, the Mostowski collapse yields a specific set ⁠\(S\)⁠ where the order relation ⁠\(x < y\)⁠ is true if and only if ⁠\(x \in y\)⁠. The resulting sets have the property that they are transitive: every element of ⁠\(S\)⁠ is also a subset of ⁠\(S\)⁠ (i.e., the union of the set is contained within the set). In this representation, each ordinal is identified with the set of all preceding ordinals.

Thus the finite von Neumann ordinals are defined recursively as ⁠\(0 = \emptyset\)⁠ and ⁠\(n+1 = n \cup \{n\}\)⁠. That is, ⁠\(1 = \{0\}\)⁠, ⁠\(2 = \{0,1\}\)⁠, ⁠\(3 = \{0,1,2\}\)⁠, etc. The first infinite ordinal ⁠\(\omega\)⁠ is represented by the set of all finite ordinals, i.e., the set of von Neumann natural numbers ⁠\(\mathbb{N} = \{0, 1, 2, \ldots\}\)⁠. Then ⁠\(\omega + 1 = \{0, 1, 2, \ldots, \omega\} = \mathbb{N} \cup \{\omega\}\)⁠, and so on.

Informally, one may define an ordinal recursively as a downward closed set of ordinals. Such a recursive definition is usually justified with the transitive closure. However, the von Neumann ordinals are already transitive sets, allowing them to be formally defined by a concise statement:

A set \(S\) is an ordinal if and only if \(S\) is transitive (every element of \(S\) is a subset of \(S\)) and strictly well-ordered by set membership (⁠\(\in\)⁠).

The set ⁠\(\omega \equiv \mathbb{N}\)⁠ is usually defined as the smallest inductive set (containing ⁠\(\emptyset\)⁠ and closed under successor). The "smallest" constraint guarantees that each element of ⁠\(\omega\)⁠ is either zero or the successor of another element of ⁠\(\omega\)⁠, which allows induction to demonstrate that ⁠\(\omega\)⁠ indeed satisfies the formal definition of ordinals stated above.

Defining the strict order relation ⁠\(<\)⁠ as the membership relation ⁠\(\in\)⁠ restricted to the class of all ordinals, the recursive characterization ⁠\(\gamma = \{\alpha \mid \alpha < \gamma\}\)⁠ is reduced to the following statement:

• If ⁠\(\alpha \in \beta\)⁠ and ⁠\(\beta\)⁠ is an ordinal, then ⁠\(\alpha\)⁠ is an ordinal: transitivity of ⁠\(\alpha\)⁠ as a set is found by finding that all the relevant ordinals are elements of ⁠\(\beta\)⁠ and then using the transitivity of the ⁠\(\in\)⁠ relation within ⁠\(\beta\)⁠; well-orderedness of ⁠\(\alpha\)⁠ follows straightforwardly from well-orderedness of ⁠\(\beta\)⁠.

The non-strict order relation ⁠\(\le\)⁠ has an alternative characterization: ⁠\(\alpha \le \beta\)⁠ if and only if ⁠\(\alpha \subseteq \beta\)⁠ for ordinals ⁠\(\alpha, \beta\)⁠. The "if" direction follows from transitivity of ⁠\(\beta\)⁠, and the "only if" direction follows from:

• If ⁠\(\alpha \ne \beta\)⁠ are both ordinals and ⁠\(\alpha \subset \beta\)⁠, then ⁠\(\alpha \in \beta\)⁠: let ⁠\(\gamma = \min\{\beta \setminus \alpha\}\)⁠. ⁠\(\alpha\)⁠ is transitive so ⁠\(\alpha = \{\xi \in \beta \mid \xi < \gamma\} = \gamma \in \beta\)⁠.

This implies that ⁠\(\le\)⁠ is a partial order. It is in fact a total order, and a well-order:

• If ⁠\(\alpha\)⁠ and ⁠\(\beta\)⁠ are both ordinals, then ⁠\(\alpha \subseteq \beta\)⁠ or ⁠\(\beta \subseteq \alpha\)⁠: ⁠\(\gamma = \alpha \cap \beta\)⁠ is an ordinal, so ⁠\(\gamma = \alpha\)⁠ or ⁠\(\gamma = \beta\)⁠, or else ⁠\(\gamma \in \gamma\)⁠, contradicting irreflexivity.
• If ⁠\(A\)⁠ is a nonempty set of ordinals, then ⁠\(\min A = \bigcap A\)⁠ must be in ⁠\(A\)⁠ by similar logic.

So all ordinal numbers form a well-ordered class ⁠\(\mathrm{ON}\)⁠, and thus any nonempty set of ordinals equipped with ⁠\(\le\)⁠ is a well-ordered set.

Specific ordinals can be constructed explicitly with the following principles:

• ⁠\(0 = \emptyset\)⁠ is an ordinal.
• For any ordinal ⁠\(\alpha\)⁠, ⁠\(\mathrm{succ}\;\alpha = \alpha \cup \{\alpha\}\)⁠ is an ordinal and ⁠\(\mathrm{succ}\;\alpha = \min\{\beta \mid \beta > \alpha\}\)⁠.
• If A is a set of ordinals, then \(\sup A = \bigcup A\) is an ordinal.

The explicit forms of ⁠\(\mathrm{succ}\)⁠ and ⁠\(\sup\)⁠ imply that for any set of ordinals, there exists another ordinal greater than all of them. In other words,

• (Burali-Forti paradox) The class of all ordinals ⁠\(\mathrm{ON}\)⁠ is not a set; otherwise ⁠\(\mathrm{succ} \sup \mathrm{ON}\)⁠ would be an ordinal not in ⁠\(\mathrm{ON}\)⁠.

Every well-ordered set \(S\) is order-isomorphic to exactly one ordinal, known as its order type. Uniqueness is guaranteed because a well-ordered set cannot be isomorphic to a proper initial segment of itself, preventing isomorphism to two distinct ordinals. The existence of this ordinal is proven by defining a map pairing each \(x \in S\) with the ordinal representing the order type of the initial segment ⁠\(S_x = \{y \in S \mid y < x\}\)⁠. By the Axiom schema of replacement, the range of this map is a set of ordinals. Because this range is downward closed (the order type of a segment of a segment is a smaller ordinal), the range is itself an ordinal \(\gamma\). The domain of the isomorphism must be all of \(S\); otherwise, the least element \(z \in S\) outside the domain would imply \(S_z \cong \gamma\), which would effectively include \(z\) in the domain, a contradiction. Thus, \(S \cong \gamma\).

Every ordinal number is one of three types: the ordinal zero, a successor ordinal, or a limit ordinal.

• Zero: The ordinal \(0 = \emptyset\) is the least ordinal.
• Successor ordinals: An ordinal \(\alpha\) is a successor if \(\alpha = S(\beta) = \beta \cup \{\beta\}\) for some ordinal \(\beta\). In this case, \(\beta\) is the maximum element of \(\alpha\).
• Limit ordinals: An ordinal \(\lambda\) is a limit ordinal if \(\lambda \neq 0\) and \(\lambda\) is not a successor ordinal.

There is variation in the definition of limit ordinals regarding the inclusion of zero. Some texts, such as Introduction to Cardinal Arithmetic by Holz et al., define a limit ordinal as a non-zero ordinal that is not a successor. In contrast, other standard set theory texts, including Jech's Set Theory and Just and Weese's Discovering Modern Set Theory, define a limit ordinal simply as any ordinal that is not a successor, which implies that 0 is a limit ordinal. When the topological definition is used (based on the order topology), 0 is not a limit ordinal because it is not a limit point of the set of smaller ordinals (which is empty); Rosenstein's Linear Orderings uses this definition. When 0 is included as a limit, ordinals that are strictly greater than 0 and not successors are usually referred to as "nonzero limit ordinals".

The following properties characterize nonzero limit ordinals:

\(\lambda\) is a nonzero limit ordinal if and only if \(\lambda \neq 0\) and for every ordinal \(\alpha < \lambda\), the successor \(S(\alpha)\) is also less than \(\lambda\).

This implies that a nonzero limit ordinal is equal to the supremum of all ordinals strictly less than it:

\(\lambda\) is a nonzero limit ordinal if and only if \(\lambda = \sup \{ \alpha \mid \alpha < \lambda \} = \bigcup \lambda\) and \(\lambda \neq 0\).

For example, \(\omega\) is a limit ordinal because any natural number is less than ⁠\(\omega\)⁠, and the successor of any natural number is also a natural number (hence less than ⁠\(\omega\)⁠). It is the least limit ordinal because each natural number ⁠\(n \in \omega\)⁠ is either zero or a successor.

Any strictly decreasing sequence of ordinals ⁠\(\alpha_0 > \alpha_1 > \alpha_2 > \cdots\)⁠ must be finite. This follows directly from the natural ordering of ordinals being a well-order: if there existed such an infinite decreasing sequence, then the set ⁠\(\{\alpha_i \mid i \in \mathbb{N}\}\)⁠ would be a set of ordinals without a least element. By the same argument, a well-ordered set has no infinite strictly descending chains; in fact, assuming the axiom of dependent choice, any total order that satisfies this condition is a well-order, giving an alternative characterization of well-ordered sets. The fact this is true for natural numbers is the basis of Fermat's method of proof by infinite descent, which can be generalized to ordinals and other well-ordered classes too, as a special case of transfinite induction where the proof of any ⁠\(P(\alpha)\)⁠ only requires ⁠\(P(\beta)\)⁠ for at most one specific ⁠\(\beta < \alpha\)⁠.

This property may be surprising when the initial value is an infinite ordinal. Indeed, for sequences starting from a natural number ⁠\(n\)⁠, the longest sequence is always one that decreases by 1 every step, leading to a sequence with ⁠\(n\)⁠ steps (⁠\(n+1\)⁠ elements). This strategy of descending to the immediate predecessor remains valid for successor ordinals. However, a limit ordinal ⁠\(\lambda\)⁠ has no immediate predecessor to descend to, so any next term must jump to some ⁠\(\beta < \lambda\)⁠, skipping infinitely many ordinals strictly between ⁠\(\beta\)⁠ and ⁠\(\lambda\)⁠. For example, when descending from ⁠\(\omega\)⁠, one must choose a finite natural number, and thus "commit" to the number of maximum remaining steps. Descending from ⁠\(\omega \cdot k\)⁠ allows one to make such a commitment ⁠\(k\)⁠ times, and descending from ⁠\(\omega^2\)⁠ allows one to commit to a finite value of ⁠\(k\)⁠. Larger ordinals may allow more complicated decision structures, but the number of descending steps remains unbounded but finite.

This property is useful for proving termination for any procedure. If the states of a computation (computer program or game) can be well-ordered, in such a way that each step is followed by a "lower" step, then the computation will terminate.

If \(\alpha\) is any ordinal and \(X\) is a set, an \(\alpha\)-indexed sequence of elements of \(X\) is a function from \(\alpha\) to \(X\). This concept, a transfinite sequence (if \(\alpha\) is infinite) or ordinal-indexed sequence, is a generalization of the concept of a sequence. An ordinary sequence corresponds to the case \(\alpha = \omega\), while a finite \(\alpha\) corresponds to a tuple, a.k.a. string.

While a sequence indexed by a specific ordinal \(\alpha\) is a set, a sequence indexed by the class of all ordinals is a proper class. The Axiom schema of replacement guarantees that any initial segment of such a class-sequence (the restriction of the function to some specific ordinal \(\delta\)) is a set.

When \(\langle x_{\iota} \mid \iota < \lambda \rangle\) is a transfinite sequence of ordinals indexed by a limit ordinal \(\lambda\) and the sequence is increasing (i.e. \(\iota < \rho \implies x_{\iota} < x_{\rho}\)), its limit is defined as the least upper bound of the set \(\{ x_{\iota} \mid \iota < \lambda \}\).

A transfinite sequence \(f\) mapping ordinals to ordinals is said to be continuous (in the order topology) if for every limit ordinal \(\lambda\) in its domain,

• if f (λ) is a limit ordinal and for every ε < f (λ) there exists a δ < λ such that for every γ, if δ < γ < λ, then ε < f (γ) ≤ f (λ), and
• if f (λ) is not a limit ordinal, there exists a δ < λ such that for every γ, if δ < γ < λ, then f (γ) = f (λ).

A sequence is called normal if it is both strictly increasing and continuous. If a sequence f is increasing (not necessarily strictly) and continuous and λ is a limit ordinal, then \(f(\lambda) = \bigcup_{\beta < \lambda} f(\beta)\).

Transfinite induction holds in any well-ordered set, but it is so important in relation to ordinals that it is worth restating here.

Any property that passes from the set of ordinals smaller than a given ordinal α to α itself, is true of all ordinals.

That is, if P(α) is true whenever P(β) is true for all β < α, then P(α) is true for all α. Or, more practically: in order to prove a property P for all ordinals α, one can assume that it is already known for all smaller β < α.

Transfinite induction can be used not only to prove theorems but also to define functions on ordinals. This is known as transfinite recursion.

Formally, a function F is defined by transfinite recursion on the ordinals if, for every ordinal α, the value ⁠\(F(\alpha)\)⁠ is specified using the set of values \(\{ F(\beta) \mid \beta < \alpha \}\).

Very often, when defining a function F by transfinite recursion on all ordinals, the definition is separated into cases based on the type of the ordinal:

1. Base case: Define \(F(0)\).
2. Successor step: Define \(F(\alpha+1)\) assuming \(F(\alpha)\) is defined.
3. Limit step: For a limit ordinal \(\lambda\), define \(F(\lambda)\) as the limit of \(F(\beta)\) for all \(\beta < \lambda\) (either in the sense of ordinal limits or some other notion of limit if the codomain allows it).

The interesting step in the definition is usually the successor step. If \(F(\alpha)\) for limit ordinals \(\alpha\) is defined as the limsup of \(F(\beta)\) for \(\beta < \alpha\) and \(F\) takes ordinal values and is non-decreasing, the function \(F\) will be continuous as defined above. Ordinal addition, multiplication and exponentiation are continuous as functions of their second argument.

The existence and uniqueness of such a function are proven by constructing it as the union of partial approximations. The proof proceeds in three steps:

1. Local Existence: For any specific ordinal δ, one proves the existence of a unique "recursion segment", a function defined on δ that satisfies the recursive rule for all ⁠\(\beta < \delta\)⁠.
2. Uniqueness and Compatibility: One proves that any two recursion segments agree on their common domain. If ⁠\(g_1\)⁠ is a segment on ⁠\(\delta_1\)⁠ and ⁠\(g_2\)⁠ is a segment on ⁠\(\delta_2\)⁠ with ⁠\(\delta_1 < \delta_2\)⁠, then ⁠\(g_2\)⁠ restricted to ⁠\(\delta_1\)⁠ is identical to ⁠\(g_1\)⁠.
3. Global Definition: The global class function F is defined as the union of all such unique recursion segments. For any ordinal α, the value ⁠\(F(\alpha)\)⁠ is the value assigned to α by any recursion segment defined on a domain larger than α.

The rigorous justification for local existence relies on the axiom schema of replacement for the step of limit ordinals in order to collect the recursion segments into a set.

This construction allows definitions such as ordinal addition, multiplication, and exponentiation to be rigorous. For example, exponentiation ⁠\(\alpha^\beta\)⁠ is defined recursively on β:

• \(\alpha^0 = 1\)
• \(\alpha^{\beta+1} = \alpha^\beta \cdot \alpha\) (for successor ordinals)
• \(\alpha^\lambda = \bigcup_{0 < \beta < \lambda} \alpha^\beta\) (for limit ordinals λ)

Condensed: the full section is in Wikipedia.