Ordinal Numbers
Natural numbers are used to two ends:
- to describe a size of a set,
- 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
Another curious order comes from the enumeration of rational numbers. If r_{n} is the n^{th} 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 r_{n} < r_{m}.
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,
Sum of ordinals
Let there be two well-ordered disjoint sets A and B with ordinals α and β. Their union
- 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. - For a∈A and b∈B, a < b.
Endowed with that order A∪B is usually denoted A + B and the corresponding ordinal
α + β ≠ β + α,
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
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
(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,
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, 1), (b, 1), (a, 2), (b, 2), (3, b), ...
which can be counted sequentially as written giving the ordinal ω for
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,
ω, ω^{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
|Contact| |Front page| |Contents| |Up| |Algebra|
Copyright © 1996-2018 Alexander BogomolnyFor two sets A and B well-ordered by the relation "≤" their product A×B is ordered by the lexicographic ordering. By definition,
Theorem
The product A×B is well-ordered by the lexicographic order.
Proof
The order is total. Indeed, given two pairs
Every subset C of A×B has the least element. Indeed, let C_{B} 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, C_{B} has the least element b_{0}. Consider all possible pairs
|Contact| |Front page| |Contents| |Up| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny