Infinity and Beyond 8: 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 earlier on this blog. 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: R → R 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 our definition of 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 by 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, in fact infinitely many.

Note: Some people think that instead of introducing a new term like ε0, we should use a more "powerful" function, like tetration, and continue the definitions.  Unfortunately, the lack of symbols to describe repeated tetration means that just introducing a new term tends to be simpler.

Infinity and Beyond 7: Cantor-Schroeder-Bernstein

The Cantor-Schroeder-Bernstein Theorem states that if, for two sets A and B, there injections A → B and B → A, then the two sets are of the same cardinality, meaning that there is an bijection A ↔ B.

Proof

We want to show that given injections f : A → B and g : B → A we can determine a one-to-one correspondence between A and B. We can and will assume that A and B are disjoint. Here's how it goes. We visualize the set A as a collection of blue dots, and the set B as a collection of red dots. We visualize the injection f as a collection of blue directed arcs connecting each element x ∈ A to its image f(x) ∈ B. Similarly, we visualize g as a collection of red directed arcs. If we put in both the blue and the red arcs, we get a directed graph where every vertex has one arc going out and at most one arc coming in.

Such a graph decomposes into a union of connected components, each of which is either a finite directed cycle, a doubly-infinite path, or a singly-infinite path. As you go along one of these paths or cycles, the vertices you encounter belong alternately to A and B. In the case of a cycle or a doubly-infinite path, the blue arcs define a one-to-one correspondence between the blue vertices of the component and the red vertices. In the case of a singly-infinite path, the blue edges will still determine a one-to-one correspondence between the blue and red vertices of the path if the path begins with a blue vertex, but not if the path begins with a red vertex. However in this latter case we can take the red edges instead. Thus we can pair up the vertices of A and B along each connected component, and the union of these correspondences determines a one-to-one correspondence between A and B.

A 2000 paper by B. Schweizer (Cantor, Schröder, and Bernstein in Orbit, Math Magazine, v 71, No, 4, October 200) offers essentially the same proof in, perhaps, a more formal format.

The four kinds of possible cycles - the connected components of A∪B - can be illustrated as follows (with a and b being generic elements of A and B:

1. a → b → a → b → ...
2. b → a → b → a → ...
3. ... → a → b → a → b → ...

4. a	→	b	→	a	→	b
   ↑						↓
   b						a
   ↑						↓
   a	←	...	...	...	←	b

The required 1-1 onto mapping φ: A → B is defined as follows:

If a belongs to a component of Type I, III, or IV, map it onto its immediate successor, i.e. let φ(a) = f(a).

If a belongs to a component of type II, map it onto its immediate predecessor, i.e., let φ(a) = g-1(a).

Infinity and Beyond 6: Cardinal Numbers

The key to a definition of Cardinal Numbers is the notion of a 1-1 correspondence. Two sets are said to be of thesame cardinality if there exists a 1-1 correspondence between the two. Two finite sets have the same cardinality only if they have the same number of elements. Their common number of elements serves to denote their cardinality. So the term finite cardinal number is a synonym for natural number. The cardinality of the set{1, 2, 3, 4, 5} is 5. Cardinality of the empty set Ø is 0. A frequent notation for the cardinality of set A is |A|, so that

|{1, 2, 3, 4, 5}| = 5

and

|Ø| = 0.

(No less frequent is another one A. I'll be using the vertical bars as more manageable in the HTML environment.)

For finite sets, the cardinality of a proper subset is strictly less than the cardinality of the set itself:

(1)	A ⊂ B and A ≠ B implies |A| < |B|.

As we know, this is not true for infinite sets. If E is the set of even natural numbers and N the set of all natural numbers then |E| = |N|. The cardinality of both is denoted  (pronounced aleph-null or aleph-zero), where  is the first letter of the Hebrew alphabet.

The fact that a proper subset of a set may have a cardinality equal to that of the set itself is often taken as thedefinition of infinite sets: a set is infinite if is contains a proper subset of the same cardinality.

For disjoint finite sets,

(2)	|A∪B| = |A| + |B|.

For disjoint sets of which at least one is infinite,

(3)	|A∪B| = max{|A|, |B|}.

The two cases can be combined if we define the addition of two cardinal numbers as the cardinality of the union of two disjoint sets with the given cardinalities. I.e., if we use (2) for any two sets A and B (whether finite or infinite), to define |A| + |B|. In this case, (3) converts to

(4)	|A| + |B| = max{|A|, |B|},

provided at least one of the sets A, B is infinite. Cardinalities corresponding to infinite sets are called transfinite.

For either finite or infinite sets, it is true that

(1')	A ⊂ B implies |A| ≤ |B|.

For finite sets,

(5)	|A| ≤ |B| and |B| ≤ |A| implies |A| = |B|.

With all the differences in behavior between finite and infinite sets, it may be surprising that (5) holds for transfinite cardinalities as well. (5) is the content of the Cantor-Schroeder-Bernstein theorem (We will discuss this next time. The theorem comes under many alternative names, e.g. the attributions Cantor-Bernstein-Schroeder theorem, Cantor-Bernstein theorem, Schroeder-Bernstein Theorem, Bernstein's theorem, all usually refer to the same statement.

In order to prove the theorem we need to pay more attention to the "≤" relation as applied to the transfinite cardinals, something we glossed over in (3) and (4).

We say that |A| ≤ |B| if there exists an injection f: A→B. Bernstein's theorem then asserts that if there exists an injection from A to B and another from B to A, then there is a 1-1 correspondence between A and B. (The proof of the theorem appears elsewhere.) We say that |A| < |B| iff |A| ≤ |B| and |A| ≠ |B|.

A subset S of a set A is categorized by a binary function f: A → {0, 1} such that S = {a∈A: f(a) = 1}. For this reason, the set of all subsets of A is denoted 2A.

Theorem

For any A, |A| < |2A|.

Proof

The proof is by the diagonal process invented by G. Cantor.

First of all, |A| ≤ |2A| because an element a of A can be identified with the 1-element set {a}. Suppose to the contrary that there is a 1-1 correspondence f: A → 2A. Function f relates to each element a of A a subset f(a) of A. There are two possibilities: either a ∈ f(a) or not. Let's define set S as a collection of the elements of a ∈ A that do not belong to their image f(a):

(6)	S = {a ∈ A: a ∉ f(a)}.

Since f is assumed to be 1-1, it is surjective: there is an s ∈ A such that S = f(s). This creates a problem.

Indeed, either s belongs to S or it does not. Let's check the first possibility first. It can't be that s ∈ S, because, by definition, S consists of those a for which a ∉ f(a). So that if s ∈ S then, too, s ∉ S. We see that it can't be that s ∈ S.But s ∉ S is also impossible, for if this were the case, s would be an element of S, by the same definition.

It follows that our assumption of the existence of a 1-1 correspondence between A and 2A leads to a contradiction. The conclusion follows: |A| < |2A|.

Starting with any set A we may construct a sequence of sets

(7)	A, 2A, 22A, 222A...

As a consequence of the theorem, the cardinalities of the sets in sequence (7) are all different. Furthermore,

(8)	|A| < |2A| < |22A| < |222A| < ...

The usual notation for the exponentiation of cardinalities is

(9)	2|A| = |2A|.

The set of real numbers, the continuum has the cardinality

c = .

(This is because the real numbers in the interval [0, 1) when represented in the binary system by the sequences of 0s and 1s can be identified (with some precautions) with subsets of real numbers.) Cantor believed but could not prove that

c = ,

i.e., the "next" cardinal number after . The assertion became known as the Continuum Hypothesis (CH): there are no cardinal numbers between  and c or, in other words,

(10)

The investigation into CH has been crowned by two results, 25 years apart, that had profound repercussion on the whole notion of the axiomatization of mathematics.

Set Theory, as developed by G. Cantor, is often termed naive as it was based on the intuitive notion of sets and their properties. Everything was a set until it was realized, first by Bernard Russell, that such an unrestricted handling of sets leads to contradictions. For example, the idea of the "set of all sets" is contradictory. To avoid such constructs and keep Set Theory contradiction-free mathematician came up with several axiomatic systems, of which the one known as Zermelo-Fraenkel (ZF) became the most popular.

In 1939, Kurt Gödel proved that CH does not contradict to ZF and, therefore, could not be disproved based on ZF. In 1963, Paul Cohen proved a similar result for the negation of CH which showed that CH can't be derived from ZF either.

There are many more cardinals than is suggested by simply constructing sequential cardinals. There are some with so peculiar construction that they are termed inaccessible (not to the human mind of course). To grasp what are these one needs the notion of a different kind of infinities, viz., the ordinal numbers.

Infinity and Beyond 5: Examples

Infinite sums

1. Geometric series: ∑n≥02−n
   20+2−1+2−2+2−3+…=2.
2. Telescoping series: ∑n≥11n(n+1)
   11⋅2+12⋅3+13⋅4+14⋅5+…=1.
3. James Gregory's (or Leibniz) series
   11−13+15−17+…=π4.
4. Euler's series: ∑n≥1n−2
   112+122+132+142+⋯=π26.
5. Euler's series: ∑n≥1(2n−1)−2
   112+132+152+172+⋯=π28.
6. Euler's alternating series: ∑n≥1(−1)n+1n−2
   1−122+132−142+152−162+⋯=π212.
7. Euler's alternating series: ∑n≥1(−1)n+1(2n−1)−3
   1−133+153−173+193−1113+⋯=π232.
8. Alternating Harmonic Series:
   11−12+13−14+…=ln(2).
9. Nilakantha (15th century) I:
   115+4⋅1−135+4⋅3+155+4⋅5−175+4⋅7+…=π16.
10. Nilakantha (15th century) II:
    3+433−3−453−5+473−7−493−9+…=π.

Infinite products

1. John Wallis' product
   2⋅2⋅4⋅4⋅6⋅6⋅…1⋅3⋅3⋅5⋅5⋅7⋅…=π2.
2. François Viète's product
   12⋅2√2⋅2+2√√2⋅2+2+2√√√2⋅2+2+22√√√√2⋅…=1π.
3. ∏n≥2(1−n−2)
   (1−122)⋅(1−132)⋅(1−142)⋅…=12.
4. ∏n≥3(1−4n−2)
   (1−432)⋅(1−442)⋅(1−452)⋅…=16.

Continued fractions

1. π
   1+122+322+522+722+…=4π.
2. more π
   1+123+225+327+429+…=4π.
3. Golden ratio
   1+11+11+11+…=ϕ=1+5√2.

What not

1. Golden ratio
   1+1+1+1√+…−−−−−−−−−−√−−−−−−−−−−−−−−−√−−−−−−−−−−−−−−−−−−−−√=ϕ=1+5√2.