Ordinal Numbers
Ordinal numbers have two related meanings. Colloquially, an ordinal number is a number that tells the position of something in a list, such as first, second, third, etc. This basic understanding extends to the meaning of ordinal numbers in set theory. In an ordered set, that is a collection of objects placed in some order, ordinal numbers (also called ordinals) are the labels for the positions of those ordered objects.
Contents
The Natural Numbers and Beyond
For example, the natural numbers \(\mathbb{N}\) have a standard ordering, which is expressed by the sequence of labels \(\{0,1, 2, 3, \ldots\}\). The integers double both as elements of \(\mathbb{N}\) and as labels for the order on \(\mathbb{N}\). This makes sense all the way up to infinite numbers. Ordinals are defined by the ordinals that come before. For instance, the ordinal \(10\) can be identified as the set \(\{0,1,2,3,4,5,6,7,8,9\}\).
The set of natural numbers is a countably infinite set. The "size" of the natural numbers as a countably infinite set is a common standard to categorize 2 types of infinite sizes: countable and uncountable. If elements of another set can be put into one-to-one correspondence with the natural numbers, that set also has a size of countably infinite.
The position of elements in finite sets are fairly obvious: they start with the natural numbers \({1, 2, 3, 4, ..., n}\), meaning \(1^\text{st}, 2^\text{nd}, 3^\text{rd},\) and so on to \(n^\text{th}.\) Note \(0\) can be an ordinal, too. After the natural numbers is the first infinite ordinal \(\omega\), and then \(\omega+1, \omega+2, \omega +3\), etc. all the way to \(\omega + \omega,\) or \(\omega\cdot2\). Then \(\omega\cdot2 + 1, \omega\cdot2 + 2\), etc. all the way to \(\omega\cdot3\). Note, it's important to express this as \(\omega + 1, \omega \cdot 2,\) or \(\omega3,\) not \( 1+\omega , 2\cdot\omega,\) or \(3\omega.\) Ordinals are not commutative, and \(1+\omega\) would be treated the same as \(1+\infty = \infty\), \(1+\omega = \omega,\) whereas \(\omega +1\) is an ordinal number decrementing one more than \(\omega\).
This is beginning to form a pattern \(\omega \cdot m+n,\) where \(m\) and \(n\) are natural numbers. This collection of ordinals is itself a set assigned the ordinal \(\omega2\). There is also \(\omega2, \omega3,...,\omega\omega,..., \omega\omega\omega,...\). And this can be continued indefinitely far. In fact, ordinals are designed to be continued indefinitely for there always to be another ordinal after the \(...\).
Total-ordered and Well-ordered Sets
Ordinals are linked to a unique kind of set called a well-ordered set. A well-ordered set is actually a type of totally-ordered set. A total-ordered set essentially means that given two elements, one will be smaller and one larger and that this distinction can be defined in a coherent manner. Formally, let \(S\) be a set. A total order on \(S\) is a binary relation, denoted by \(\le \), such that for all \(a, b, c \in S\), the following axioms hold:
- Either \(a\le b\) or \(b \le a\).
- If \(a\le b \) and \(b\le a\), then \(a=b\).
- If \(a\le b\) and \(b\le c\), then \(a\le c\).
For example, the standard ordering on \(\mathbb{R}\) is a total order \({0,1,2,3,4,5,6,...}\). As a consequence, the dictionary order, meaning the commonly understood order like \({a_1,a_2,a_3,...,a_k,...,b_1,b_2,...,b_k,...,c_k}\) on \(\mathbb{R}^n\) is also a total order. This is defined by setting \[(x_1, x_2, \ldots, x_n) \le (y_1, y_2, \ldots, y_n)\] iff \(x_i \le y_i\) in the standard ordering on \(\mathbb{R}\) for all \(1\le i \le n\).
Back to well-ordered sets and ordinals! A well-ordered set is a total-ordered set with no infinite decreasing sequences. Ordinals may label the elements of the well-ordered set to measure the length of the whole set by the least ordinal that is not a label. Note that \(\mathbb{R}\) with the standard ordering is not well-ordered, since for every element \(x\in \mathbb{R}\), the element \(y:= x-1 \in \mathbb{R}\) satisfies \(y \le x\). However, the natural numbers \(\mathbb{N}\) with their natural ordering are well-ordered, by the well-ordering principle.
Two sets \(A\) and \(B\), with total orders \(\le_{A}\) and \(\le_{B},\) respectively, are called order-isomorphic if there exists a bijection \(f: A \to B\) such that \(a \le_{A} b\) implies \(f(a) \le_{B} f(b)\) for all \(a,b \in A\).
Constructing Ordinal Numbers
Suppose that a sequence of ordinal labels has been constructed. Then, every ordinal \(x\) describes a well-ordered set, namely the set of all ordinals less than \(x\). This set, which we also denote by \(x\), can be thought of as the canonical example of a particular well-ordered set, in the sense that it represents the equivalence class of all well-ordered sets that are order-isomorphic to it.
To illustrate this, consider the finite ordinal \(5\), which one identifies with the ordered set of ordinals less than it, namely \(5 = \{0, 1, 2, 3, 4\}\). Then, any well-ordered four-element set (0 is the ordinal label for a non-element, for the zeroth element) is order-isomorphic to \(5\); for example, the four-element set \(\{a,b,c,d\}\) with well-order \(b\le a \le d\le c\) permits the order-isomorphism \(f: 5 \to \{a,b,c,d\}\) given by \(f(1) = b\), \(f(2) = a\), \(f(3) = d\), and \(f(4) = c\).
Based on this intuition, one formally defines ordinals as equivalence classes of well-ordered sets. If \((A, \le _{A})\) and \((B, \le_{B})\) are well-ordered sets, then one writes \(A \sim B\) if \(A\) and \(B\) are order-isomorphic; this relation \(\sim\) is an equivalence relation, and the equivalence classes obtained are called ordinals. Denote by \([A]\) the equivalence class of \(A\), i.e. the ordinal containing the well-ordered set \(A\).
In this formalism, the finite ordinals are precisely \(1:= [\emptyset], 2:= [\{1\}], 3:= [\{1, 2\}], 4:=[\{1,2,3\}], \ldots\). The smallest infinite ordinal is \(\omega := [\mathbb{N}]\). For an example of an infinite ordinal larger than \(\omega\), consider the set \(S:= \mathbb{N} \cup \{\star\}\) with well order \[1 \le 2 \le 3 \le \cdots \le \star.\] Since \(S\) does not have the same cardinality as \(\mathbb{N}\), the ordinal \([S]\) does not equal \(\omega\). Usually, one denotes \(\omega + 1 := [S]\).
References
- Pop-up Casket, . Omega-exp-omega-labeled. Retrieved January 24th, 2017, from https://commons.wikimedia.org/wiki/File:Omega-exp-omega-labeled.svg