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 extend 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, \cdots\}\). The integers double as both 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}\).
Because natural numbers are finite, the size of an infinite set cannot be measured by natural numbers. Instead infinite sets are measured by cardinal numbers and ordered by ordinal numbers. This difference is important because every set has only one size, but some sets can have multiple well-orderings, and therefore elements of the sets can have different positions.
The position of elements in finite sets are fairly obvious, they start with the natural numbers \({1, 2, 3, 4, ...n}\), meaning 1st, 2nd, 3rd, and so on to nth. Note \(0\) can be an ordinal too. After the natural numbers is the first infinite ordinal, \(\omega\), 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, \cdots, x_n) \le (y_1, y_2, \cdots, 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 and 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\}], \cdots\). 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