# Ordinal Numbers

Natural numbers are used to two ends:

1. to describe a size of a set,
2. to indicate the position of an element in a sequence of elements.

Grammatically, the numbers that describe the size - one, two, three, and so on - are nouns. The numbers that describe the position - first, second, third, etc. - are adjectives.

G. Cantor extended the counting by introducing both transfinite sizes and transfinite positions. Correspondingly, in the Cantorian set theory, there are two kinds of entities: cardinal and ordinal numbers. Cardinal numbers have been discussed elsewhere. Here we talk of ordinal numbers.

The set N of natural numbers is naturally ordered: 1, 2, 3, 4, ... But this is not the only order the numbers may be arranged in. For example, the famous Sarkovskii's theorem lists the natural numbers starting with all the odd numbers, followed by the odd numbers times the increased powers of two (a power of 2 at a time) and closing by the powers of 2 in the decreasing order:

3, 5, 7, ...,
2·3, 2·5, 2·7, ...,
2²·3, 2²·5, 2²·7, ...,
... 2³, 2², 2, 1.

(The theorem states that if a real function f: RR has an orbit of period n and m comes after n in the above ordering, then f has an orbit of period m.)

Another curious order comes from the enumeration of rational numbers. If rn is the nth rational number according to a particular enumeration we may define a total dense order on the set N of natural numbers by

n < m iff rn < rm.

However, here we are concerned only with well orderings of N. The term for an ordering of a well ordered set is ordinal number or just ordinal.

The natural order of N is denoted ω and is the first transfinite ordinal. Every positive integer is a finite ordinal.

If a well-ordered set A with the ordinal α is similar to a subset of a well-ordered set B with the ordinal β then, by definition, α ≤ β. In particular, for every finite n, n ≤ ω. However, since there is no injection, let alone an order-preserving one, from N into a finite set, we may claim that n ≠ ω and n < ω.

### Sum of ordinals

Let there be two well-ordered disjoint sets A and B with ordinals α and β. Their union C = A∪B may be endowed with a well-ordering the following way:

1. For a∈A and b∈A or for a∈B and b∈B, a ≤ b provided the same is true in either A or B.
2. For a∈A and b∈B, a < b.

Endowed with that order A∪B is usually denoted A + B and the corresponding ordinal α + β. (The set A∪B is indeed well ordered: its order is total and every subset contains a minimum element.) In general,

α + β ≠ β + α,

i.e., the addition of the ordinals is not commutative (it is commutative if the two are finite.)

Obviously, ω is greater than any natural number so that the set N∪{ω} assumes naturally a well-ordering of N + {ω}

1, 2, 3, ..., n, ..., ω.

By the definition of the addition, the ordinal number of this set is

ω + 1.

On the other hand, also by the definition, 1 + ω is the ordering of, say, {ω} + N:

ω, 1, 2, 3, ..., n, ... .

which is similar to N. (Just use the shift f(n) = n-1, n>1 and f(1) = ω.) It follows that

 (1) 1 + ω = ω.

We see that 1 + ω = ω ≠ ω + 1. The fact that 1 + ω = ω underlies the famous story of Hilbert's Hotel Infinity. This a remarkable hotel that has rooms with every possible (natural) number which, according to the story, happened to be full when a new arrival sought to stay overnight. As there was no sign "NO VACANCY" flashing on the outside, the fellow was dismayed to learn that the hotel was full. However, at the Hotel Infinity, this did not mean the absence of accommodation. The manager simply asked the guests to move one room up thus freeing room #1 which he offered to the new arrival.

ω + ω is the ordinal of, say, E + O, where E and O are the sets of even and odd numbers with the natural order.

ω + ω ≠ ω

because the subset {2, 4, ..., 1} of E + O has a largest element 1 while no infinite subset of N has a largest element.

Is there a shorthand for expressions like ω + ω. One (or both) of 2ω and ω·2 seems as an appropriate candidate. We'll see shortly that only one will do.

### Product of ordinals

For two sets A and B well-ordered by the relation "≤" their product A×B is well-ordered by the lexicographic ordering. By definition, (a1, b1) ≤ (a2, b2) if either b1 < b2 or b1 = b2 and a1 < a2.

According to this definition, N×{a, b} is ordered as

(1, a), (2, a), (3, a), ..., (1, b), (2, b), (3, b), ...

and is of type ω + ω. On the other hand, {a, b}×N is ordered as

(a, 1), (b, 1), (a, 2), (b, 2), (3, b), ...

which can be counted sequentially as written giving the ordinal ω for {a, b}×N.

In general, the product A×B of two sets with ordinals α and β, ordered lexicographically, as above, is well-ordered and is assigned the ordinal denoted α·β (or just αβ.) The above example tells us that

2·ω = ω ≠ ω + ω = ω·2.

Next, let's have a look at ω·ω, the ordinal corresponding to the lixicographically ordered product N×N. The product consists of all (ordered) pairs of natural numbers ordered as

(1, 1), (2, 1), (3, 1), ...,
(1, 2), (2, 2), (3, 2), ...,
(1, 3), (2, 3), (3, 3), ...,
...

Naturally, the shorthand is ω² = ω·ω. Further, ω³ is the ordinal corresponding to the lexicographic order of N×N×N. (The latter is a natural extension of the definition given for two factors.) ω³ = ω²·ω, etc.

For any ordinal α there is a unique element "just after" α. It is called the successor (of α) and is the least ordinal among all those ordinals that exceed α. This is, of course, α + 1. However, the are ordinals that do not succeed any single ordinal. (ω is one such example.) These are called limit ordinals. Limit ordinals are the least ordinals that exceed all ordinals from an infinite set. Fro example, we may continue introducing the powers of ω:

ω, ω2, ω3, ω4, ...

The least ordinal that exceeds all natural powers of ω is denoted ωω and this shows a new way to expand the set of the ordinals:

 (2) ωω, ωωω, ωωωω, ...

There is the least ordinal that solves Cantor's equation ωε = ε. This is denoted ε0 (pronounced epsilon-null, epsilon-nought, epsilon-zero.) This is the first inaccessible ordinal, i.e. the ordinal which can't be expressed as a combination of various powers of ω. But there are more ...  For two sets A and B well-ordered by the relation "≤" their product A×B is ordered by the lexicographic ordering. By definition, (a1, b1) ≤ (a2, b2) if either b1 < b2 or b1 = b2 and a1 < a2.

### Theorem

The product A×B is well-ordered by the lexicographic order.

### Proof

The order is total. Indeed, given two pairs (a1, b1) and (a2, b2), since B is well ordered, either b1 ≤ b2 or b1 ≥ b2. Assume the first. Then either b1 < b2 or b1 = b2. In the former case we finished for, by the definition, then (a1, b1) ≤ (a2, b2). In the latter case, we compare the first components. The result is always definite because A is well-ordered.

Every subset C of A×B has the least element. Indeed, let CB be the projection of C on B, i.e., the set of all b's for which there is an a from A such that (a, b) is in C. Being a subset of B, CB has the least element b0. Consider all possible pairs (a, b0) in C. Their first component form a subset of A with a minimum element a0. The pair (a0, b0) is then the least element of C.  