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.