Monday, March 5, 2012

Infinity: Countable Ordinals

This is the eighth post of the Infinity Series. For the first post, see here. For all posts, see the Infinity Series Portal.

In the previous posts (here and here), ordinal numbers and basic operations concerning them were introduced. Now, using exponentiation, the ordinal ω2 can be defined. By the definition of exponentiation,

ω2 = ω*ω,

which is greater than any ordinal ω*n, for all natural numbers n, and is therefore greater than ω. ω2 as a set is written {0,1,2,...,ω,ω + 1,...,ω*2,ω*2 + 1,...,ω*3,...,ω*n,...}.

In contrast, consider 2ω, which is the limit of 2n over natural numbers. Clearly, this is just the limit of a sequence of increasing natural numbers, namely ω. Therefore, 2ω = ω. In the same way, one can define further ordinals of the form ωn, and confirm that nω = ω for all natural numbers n.

To prove that ordinals such as ωn are countable, one must use the following theorem:

The union of countably many countable sets is countable. (1)

Besides being a mouthful, this theorem is invaluable in confirming the countability of sets. To see how the theorem works, consider a countable set of countable sets {A,B,C...} (each of A, B, C, etc. is a countable set). Since this set is countable, the sets in this set can be labeled with natural numbers. Each set can then be identified with, and written, as a number, (for clarity, the numbers will be in boldface), with A = 1, B = 2, C = 3, and so on. Since each of these sets individually is countable, the elements of each one can be labeled 1, 2, 3 and so on. For example, the element labeled "1" in set A will be denoted 11. We now construct the following function for labeling the elements of all of the above sets (the first ten values, corresponding to the natural numbers 1-10, are shown)

1→ 11, 2→ 12, 3→ 21, 4→ 13, 5→ 22, 6→ 31, 7→ 14, 8→ 23, 9→ 32, 10→ 41,...

It is easily calculated that the general member m of any set n can be found by the following formula:

((m + n)(m + n - 1))/2 - n + 1→ nm

This formula may seem rather complicated, but the important fact is that for any element of any set in {A,B,C...}, there is exactly one natural number that serves as its "label", and the above sequence is a one-to-one correspondence.

We first observe that ω2 is countable, as it is a union of all sets of the form {ω*n + 0, ω*n + 1,...} for natural n. Each of these is countable, as every set of the above form can be put into a one-to-one correspondence with the natural numbers simply by dropping the ω term from each member, and the set of all these sets is also countable, as there is one for each natural number n. (1) is therefore applicable, and ω2 is countable.

Similarly, one can define a set of sets of the form {(ω2)*n,(ω2)*n + 1,...,(ω2)*n + ω,(ω2)*n + ω + 1,...,(ω2)*n + ω*2,...,(ω2)*n + ω*3,...,(ω2)*n + ω*m,...}. If n = 0, then the set above reduces to ω2. For all other values of n, the set can be put into a one-to-one correspondence with ω2 by dropping the first term. The union of all these sets, with the set of sets being, of course, countable, is ω3.

The above outlines a recursive scheme that confirms that all ωn are countable. The countability of each power of ω allows one to apply (1) to the next power. Therefore, if one repeats this process indefinitely over all natural numbers, the limit is the ordinal ωω, which is again countable, being a limit of countably many countable sets. The property of such a limit being countable is very important to ordinal numbers and will be used often. It is a consequence of the theorem proved above, and will be referred to by (2).

This fact seems at odds with what was previously discussed about cardinal numbers, with 20 being equal to the cardinality of the continuum, which describes a property of uncountable sets. It seems much "easier" in a sense to access uncountable cardinals than it is to describe uncountable ordinals, and it will soon be described just how difficult the latter is.

Continuing from ωω, one can use a similar recursive scheme to show that ωω2, ωω3, and so on, are countable. Remarkably, under the same limiting process, combined with recursion, ωωω, ωωωω, and any larger finite power towers of ω are countable.

At this point, no larger ordinals can be described through the operations of addition, multiplication, and exponentiation directly in terms of ω. We therefore define the ordinal ε0 (epsilon-nought) as the limit of the sequence ω, ωω, ωωω, ωωωω,..., or, more formally, as the smallest ordinal α such that ωα = α. In other words, this ordinal is so large that the two quantities ωε0 and ε0 are indistinguishable. Mathematically, ε0 is also the smallest fixed point of the map α → ωα, i.e. is left unchanged when it is applied.

Remarkably, ε0, despite being extremely large, is still countable! It is the limit of the set {ω, ωω, ωωω, ωωωω,...,ω↑↑n,...}, where ↑↑ represents the hyper4 operator, or iterated exponentiation, which in this case a shorthand for writing "n ω's in the power tower". Since, in this set, n takes only natural number values, the set itself is countable, and ε0 is the limit of countably many countable ordinals, and, by (2), is itself countable.

Of course, ordinals do not end here. One can go on to define ε0 + 1, ε0*2, ε0ω and others. For the same reasons as the corresponding expressions involving ω, these are all countable. One can go to on to define the limit of the set {ε00ε00ε0ε0,...,ε0↑↑n,...} as a new ordinal, ε1. Reviewing the process through which this ordinal was created, one can see that it is a limit of a set of limit ordinals, each of which was itself a limit of a sequence of ordinals! Despite being so far removed from our original ω, it is again countable, by the same logic used for ε0. Also, this is the second fixed point of the map mentioned above, as all ordinals between ε0 and ε1 are not equal to themselves under
α→ ωα, e.g. ωε0 + 1 = ωε0*ω = ε0*ω ≠ ε0 + 1.

Continuing even further, one can define εα for any natural number α. The formula below shows how this is done, with the symbol "sup{}", representing the supremum, or least ordinal greater than or equal to every member, of a set. Essentially, the notation "supremum of a set" is interchangeable with "limit of a sequence", but the former is easier to write. The formula for εα is recursive, using succession to define each member of the epsilon sequence.

εα' = sup{εααεααεαεα,...,εα↑↑n,...}

Since each set in the above equation is countable, and each ordinal involved is countable, the members of the epsilon sequence for finite α are countable. Of course, one can then construct a set of all epsilon ordinals of natural number index α, i.e. {ε012,...,εα,...}. This set is countable, as well as all of its members, and it therefore has a countable supremum, which can be defined as εω. Subsequently,
εω + 1, εω + 2,...,εω*2, and others can be defined. Each of these ordinals, if the subscript of ε is limit ordinal, is simply the supremum of all previous members of the epsilon sequence. Otherwise, the subscript is the successor to some other ordinal, and the formula that was used for ε ordinals of finite indices can be applied.

An important property of the epsilon sequence is that any ordinal in the sequence with a countable index is also countable. This is because, for such an ordinal, the set of all previous members of the epsilon sequence is countable. The reason for this is that they can be easily put into a one-to-one correspondence with a countable set, simply by dropping the "ε", and considering only their indices. For example, εω*2 is the supremum of the set
A = {ε012,...,εωω + 1,...}. A bijection can be constructed from this set to ω*2, namely the one assigning ε0→0, ε1→1, etc., confirming the countability of A and the applicability of (2).

Among the epsilon ordinals of countable index are εωω, εωωω, and even εε0. But where can one go from here? This is still just the beginning of infinite ordinals. More are explored in the next post.

Sources: Axiomatic Set Theory by Patrick Suppes,, Large Numbers at MROB

No comments: