Infinity: Ordinal Numbers

This is the sixth post in the Infinity Series, the first of which is found here. For all posts, see the Infinity Series Portal.

In order to further explore the concept of infinity, one must temporarily move away from the concept of the cardinal number, and consider yet another type of number: the ordinal. The system of ordinal numbers is again entwined in set theory, and, unlike cardinal numbers, they can be expressed as sets. It is also important to know that any cardinal number can alternatively describe a family of sets, i.e. all of the sets that have that cardinality. For example, the cardinal number 3 not only describes a number of members that a set can have, but also represents the family of all sets with three members.

Formally, ordinal numbers are very similar to cardinal numbers in that, in finite situations, they represent properties of classes of sets. The property that an ordinal number represents is known as order type. However, the class of sets whose order type is described by an ordinal number much more specific than that of a cardinal number. To understand the type of set that has an order type can represent, one must first understand the concept of a well-ordered set.

A well-ordered set is a set that can be well-ordered by a relation. A relation, in this case, is just a quantity that connects pairs of elements. A good example is the relation "<" or "less than". To understand well-ordering, observe the example below.

Consider the set S = {2,5,7}, and the relation R = <
If "<" is restricted to the set S, it simply means that the two elements of each ordered pair of the relation must come from S, i.e. chosen from 2, 5, or 7. Of the six possible ordered pairs, (2,5), (2,7), (5,7), (5,2), (7,2), and (7,5), three are members of the relation <, namely (2,5), (2,7), and (5,7). This is because 2<5, 2<7, and 5<7. Obviously, the remaining pairs are not, as 5 is not less than 2, and so on.

In this case, "<" well-orders S, meaning that each (non-empty) subset of S has a "minimal" element. For the relation "<", the "minimal" element of a subset is simply its smallest member. Since it is easy to find the smallest number of any subset of S, it is a well-ordered set.

In contrast, consider the set of all whole numbers N = {1,2,3...}. The above relation "<" does well-order the set, because, for any subset, one can state the smallest element. However, this does not hold with the operation "greater than" or ">". For example, if the subset N' is the set of natural numbers greater than 3, i.e. {4,5,6...}, then there is no "minimal" element under the relation ">", as there is no element in the set that is greater than all the others. However, overall, the set is still "well-ordered", because there is at least one relation that does satisfy the needed conditions.

Now, returning to the class of sets a certain order type, consider all the well-ordered sets that can be put into one-to-one correspondence (i.e. all the well-ordered sets with a given cardinality). However, this correspondence is of a rather special type, matching up the "minimal" elements with each other, followed by the "next-to-minimal" elements, and so on. Every class of sets for which all the members are connected is an equivalence class, and all sets in this class have an identical order type, which is a certain ordinal number.

For instance, the above set S = {2,5,7} under "<", and the set T = {b,c,d} under the relation that will be defined as "alphabet" (which puts alphabet in order), can be related by a correspondence. The minimal element of set S under "<" is clearly 2, and the minimum of T under "alphabet" is b, with b being the letter in the set closest to the beginning of the alphabet. Since the other elements can be paired in a similar way, these two sets are therefore members of an equivalence class and are of the same order type (intuitively, they are this order type because they each have three elements).

However, for each equivalence class, it is convenient to chose one, and only one set to be representative of the entire class, and thus, the ordinal. The first such set is the empty set, Ø, having no elements and being the only member of its equivalence class. We identify this set with the ordinal number "0". Therefore,

0 = Ø = {}

Hence forth, the representative set of each equivalence class is defined as the set containing all of the previous representative sets. For example, the successor of 0 is denoted "1", or the second ordinal number, and is defined as

1 = {Ø}

Note that this set is not the empty set, but rather the set containing only the empty set. It is obvious that this set can be well-ordered, as, trivially, there is only one element to order. It is equally clear that this set is representative of the class of sets with a single element and that it can be put in a one-to-one correspondence with each set in that class. Continuing the pattern of each representative set containing all of those previously, we have

2 = {Ø, {Ø}},
3 = {Ø, {Ø}, {Ø, {Ø}}},
and so on. Note that "2", has 0 and 1 as members, and "3" has 0, 1, and 2 as members.

Henceforth, "ordinal number" will refer to a set of this type, and 0, 1, 2, 3,... will refer to ordinal numbers unless otherwise specified. These ordinal numbers are well-ordered by the membership relation, or the relation set up between two sets with the second containing the first. In other words, each element of an ordinal number set is a member of all subsequent elements in the set. For example,

4 = {Ø, {Ø}, {Ø, {Ø}}, {Ø, {Ø}, {Ø, {Ø}}}}

In this set, each member is a member of each subsequent member, namely, Ø, being the first element of 4, is a member of {Ø}, {Ø, {Ø}}, and {Ø}, {Ø, {Ø}}}, which, of course, are just the ordinal numbers 1, 2, and 3. The minimal element for each ordinal number is Ø.

It is clear that one can go on to define any natural number as a set of this type, namely as the set of all previous ordinals. As with cardinal numbers, the first infinite ordinal number corresponds to the set of all natural numbers. This ordinal is denoted ω, and has every (ordinal) natural number as a member. It is clear that this set can be put in a one-to-one correspondence with the set of "regular" natural numbers, and it therefore has a cardinality of aleph-zero. However, the world of infinite ordinals is very different than that of infinite cardinals.

One crucial difference is the idea of succession in ordinals. From any ordinal α (greek letters are often used for ordinal variables), there is a successor to α, denoted α', which is defined as the next ordinal after α. Formally, α' is the smallest ordinal which has α as a member. Furthermore, α' can be constructed using the formula

α' = α ∪ {α}

where ∪ is the symbol for a union of sets. The concept of union entails combining all the members of two sets into one, and deleting any duplicates. For instance,

{1,4,6} ∪ {3,6,13} = {1,4,6,3,6,13} => {1,4,6,3,13}

Returning to the succession formula above, note the distinction between α and {α}. The first is an ordinal, but the second is not, being rather a set containing a single ordinal, α, as its only member. To more easily visualize this process, consider the simplest example:

0 = Ø
0' = Ø ∪ {Ø}

Now, the union of the empty set with any other set is simply the other set, as the empty set contributes no members to the result. Therefore,

0' = Ø ∪ {Ø} = {Ø},

the final term of which is, in fact, the ordinal 1! Though ordinal addition has not been defined, we can observe that the succession operation, in a more general case, identifies with the process of adding 1 (0+1=1 and 0'=1, etc.). The role that succession plays in infinite ordinals, as well as in operations on ordinals, is considered in the next post.

Sources: Axiomatic Set Theory by Patrick Suppes