nLab ordinal number

Redirected from "ordinal".
Ordinal numbers

Context

Arithmetic

(0,1)(0,1)-Category theory

Ordinal numbers

Idea

The ordinal numbers (or just ordinals) constitute a generalisation of a natural numbers to numbers of possibly infinite magnitudes. Specifically, ordinal numbers generalise the concept of ‘the next number after …’ or ‘the index of the next item after …’. In particular, the next number after the natural numbers is the first infinite ordinal number.

Definition

Naïvely, an ordinal number should be an isomorphism class of well-ordered sets, and the ordinal rank of a well-ordered set SS would be its isomorphism class. That is:

  1. every well-ordered set has a unique ordinal number as its ordinal rank;
  2. every ordinal number is the ordinal rank of some well-ordered set;
  3. two well-ordered sets have the same ordinal rank if and only if they are isomorphic as well-ordered sets.

Then a finite ordinal is the ordinal rank of a finite set, while an infinite ordinal or transfinite ordinal is the ordinal rank of an infinite set. (If you interpret both terms in the strictest sense, then there may be ordinals that are neither finite nor infinite, without some form of the axiom of choice).

Taking this definition literally in material set theory, each ordinal is then a proper class (so one could not make further sets using them as elements). For this reason, in axiomatic set theory one usually defines an ordinal number as a particular representative of this equivalence class. One particularly slick definition is due to von Neumann:

  • An ordinal is a transitive pure set XX which is well-ordered by the membership relation \in. Then the ordinal rank of a well-ordered set SS is the unique ordinal number that is isomorphic (as a well-ordered set) to SS; it is a theorem that this exists, satisfying (1–3).

These pure sets are the von Neumann ordinals. In the presence of the axiom of foundation, \in is automatically a well-founded relation, so it suffices to require that \in be a transitive relation on X +=X{X}X^+ = X \cup \{X\}.

In the appendix of John Kelley‘s topology textbook, ordinals are defined as:

  • An ordinal is a class XX such that every element of XX is a subset of XX and for all A,BXA,B \in X, either ABA \in B, BAB \in A or A=BA=B.

It is later proven that in the axiomatic setting of the appendix (Morse-Kelley set theory), ordinals are sets.

From the perspective of structural set theory, it breaks the principle of equivalence to care about distinctions between isomorphic objects, and unnecessary to insist on a canonical choice of representatives for isomorphism classes. Therefore, from this point of view it is natural to simply say:

However, one still may need sets of ordinals, that is sets that serve as the target of an ordinal rank function satisfying (1–3) on any (small) collection of well-ordered sets. One can construct this as a quotient set of that collection.

Properties

The class of ordinals is itself well-ordered. There are many equivalent ways to define this ordering. One is that α<β\alpha\lt\beta iff α\alpha is isomorphic to a proper initial segment of β\beta (that is, a subset SβS\subsetneq \beta such that bSb\in S and a<ba\lt b imply aSa\in S). With the von Neumann definition, this is equivalent to simply saying that αβ\alpha\in\beta.

Every ordinal α\alpha has a successor α +\alpha^+, which in the von Neumann definition is simply α +=α{α}\alpha^+ = \alpha \cup \{\alpha\}. A limit ordinal is any ordinal which is not a successor of any other ordinal.

In the presence of the axiom of choice, a cardinal number can be defined as a special ordinal number, specifically an ordinal which is not equipollent (isomorphic as a set) to any smaller ordinal.

One important use of ordinals is to index transfinite constructions, such as:

 References

For ordinal numbers in homotopy type theory, see section 10.3 of:

On the equivalence of set-theoretic and type-theoretic ordinals, see:

Basic set-theory including ordinals is developped in the appendix of:

Last revised on December 27, 2023 at 18:54:28. See the history of this page for a list of all contributions to it.