Infinity: Operations on Ordinals

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

In the previous post, the concept of ordinal numbers was introduced, as well as the idea of succession. Now, one can build the idea of ordinal addition by considering iterated succession. In the definition of ordinal addition, a recursive scheme is used, with succession as each step in the addition process.

The definition of addition is as follows for two (finite) ordinals α and β:
α + 0 = α
α + β' = (α + β)'

This procedure works for any finite ordinals (natural numbers). For example, the sum of 4 and 3 is

4+3 = 4+2' = (4+2)' = (4+1')' = ((4+1)')' = ((4+0')')' = (((4+0)')')') = (((4)')')' = ((4')')' = (5')' = 6' = 7

However, when attempting to evaluate the addition of infinite ordinals, one encounters a snag. Consider the ordinal ω, which is the set of all finite ordinals (natural numbers). For example, one cannot evaluate 1 + ω using the previous rule, as ω is not the successor of any ordinal, as it is the limit of the natural numbers. Ordinals which cannot be expressed as successors of others are accordingly known as limit ordinals.

The succession scheme above leads to all the familiar properties of addition for natural numbers, commutativity, associativity, and the like. However, the addition of infinite ordinals does not possess all of these properties. Consider the sum ω+1. The succession-based addition scheme works here, as

ω + 1 = ω' = ω∪{ω},

or, in more familiar set notation, the set of ordinals

ω + 1 = {0,1,2,3...,ω}, which is not equal to ω, as it has ω as a member, and no ordinal has itself as a member, only all previous ordinals. Therefore, unlike in cardinal addition, where adding any natural number to ℵ₀ leaves it unchanged, ω + 1 is distinct from ω.

However, now consider 1 + ω. Although this expression cannot be evaluated using the previous method, one can intuitively think of the addition as the limit over natural numbers n of

1 + n,

which simply is, as n increases without bound among the natural numbers, ω. This is because the limit of a sequence of natural numbers can never exceed ω.

1 + ω = ω ≠ ω + 1

Paradoxically, these ordinals are different, but have the same cardinalities, namely ℵ₀. To reinforce this fact, one can readily identify a one-to-one function f from ω + 1 to ω defined in the following way:

f(α) = α + 1, if α ≠ ω and f(α) = 0, if α = ω

Therefore, f(0) = 1, f(1) = 2, and so on, with each natural number being mapped to another, clearly within the range, ω, and the final member of ω + 1, ω, being mapped to 0. The methods used here are similar to those that were earlier used to demonstrate cardinal equalities.

In a similar fashion, 2 + ω = ω, and for that matter n + ω = ω for any natural number n. Also, ω + n > ω for any n ≥ 1, being instead equal to the set {0,1,2,3...,ω,ω + 1,ω + 2,...,ω + n - 1}

Ordinal multiplication can now be introduced as iterated addition, with

α*0 = 0
α*β' = α*β + α

Trivially, by this definition, ω*1 = ω*0 + ω = ω. Also, 1*ω is the same as the operation "+1" iterated for each natural number, i.e. an infinite number of times. In the same way as 1 + ω, 1*ω = ω.

However, what about ω*2? By the definition of multiplication it is equal to ω + ω. Clearly this is greater than ω and is equal to the set of ordinals {0,1,2,...,ω,ω + 1,ω + 2,...}. However, 2*ω is the limit of 2*n as n increases through the natural numbers. In the same way as 1 + ω, 2*ω = ω, hence ordinal multiplication is not commutative.

The above cases can be generalized to any ordinal of the form ω*m + n. Such an ordinal is strictly greater than ω, but is countable, i.e. there exists a bijection from this set to ω. Such a function is easily constructible along the lines of the linear function y = mx + n. To illustrate this process, consider the example ω*2 + 3 = {0,1,2,...,ω,ω + 1,ω + 2,...,ω*2,ω*2 + 1,ω*2 + 2,ω*2 + 3}. The function from this ordinal to ω is constructed as follows:

0 -> 3, 1 -> 5, 2 -> 7,... (finite ordinals α transform to α*2 + 3)
ω -> 4, ω + 1 -> 6, ω + 2 -> 8,... (ordinals of the form ω + α, for finite α, transform to α*2 + 4)
ω*2 -> 0, ω*2 + 1 -> 1, ω*2 + 2 -> 2

Clearly, this assigns a unique natural number (member of ω) to each element of the set ω*2 + 3, and the latter set is therefore countable, with a cardinality of ℵ₀. All ordinals of the form ω*m + n have this same cardinality.

Finally, to extend the system of infinite ordinals further, one must introduce ordinal exponentiation, defined as follows:

α⁰ = 1
α^β' = (α^β)*α

For limit ordinals, the same limit argument used before will apply. Using these three operations, together with the idea of a limit, one can define many other infinite countable ordinals, a topic explored in the next post.

Sources: Axiomatic Set Theory by Patrick Suppes, http://en.wikipedia.org/wiki/Ordinal_addition