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 ω² can be defined. By the definition of exponentiation,

ω² = ω*ω,

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

In contrast, consider 2^ω, which is the limit of 2ⁿ 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 ωⁿ, and confirm that n^ω = ω for all natural numbers n.

To prove that ordinals such as ωⁿ 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 1₁. 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→ 1₁, 2→ 1₂, 3→ 2₁, 4→ 1₃, 5→ 2₂, 6→ 3₁, 7→ 1₄, 8→ 2₃, 9→ 3₂, 10→ 4₁,...

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→ n_m

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 ω² 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 ω² is countable.

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

The above outlines a recursive scheme that confirms that all ωⁿ 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 2^ℵ₀ 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 ε₀ (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 ω^ε₀ and ε₀ are indistinguishable. Mathematically, ε₀ is also the smallest fixed point of the map α → ω^α, i.e. is left unchanged when it is applied.

Remarkably, ε₀, 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 ε₀ 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 ε₀ + 1, ε₀*2, ε₀^ω 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 {ε₀,ε₀^ε₀,ε₀^ε₀ε₀,...,ε₀↑↑n,...} as a new ordinal, ε₁. 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 ε₀. Also, this is the second fixed point of the map mentioned above, as all ordinals between ε₀ and ε₁ are not equal to themselves under
α→ ω^α, e.g. ω^{ε₀ + 1} = ω^ε₀*ω = ε₀*ω ≠ ε₀ + 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. {ε₀,ε₁,ε₂,...,ε_α,...}. 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 = {ε₀,ε₁,ε₂,...,ε_ω,ε_{ω + 1},...}. A bijection can be constructed from this set to ω*2, namely the one assigning ε₀→0, ε₁→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, http://en.wikipedia.org/wiki/Epsilon_nought, Large Numbers at MROB