Calculus of Real and Complex Variables

1.2 The Schroder Bernstein Theorem

It is very important to be able to compare the size of sets in a rational way. The most useful theorem in this context is the Schroder Bernstein theorem which is the main result to be presented in this section. The Cartesian product is discussed above. The next definition reviews this and defines the concept of a function.

It is probably safe to say that most people do not think of functions as a type of relation which is a subset of the Cartesian product of two sets. A function is like a machine which takes inputs, x and makes them into a unique output, f

. Of course, that is what the above definition says with more precision. An ordered pair, which is an element of the function or mapping has an input, x and a unique output y,denoted as f while the name of the function is f. “mapping” is often a noun meaning function. However, it also is a verb as in “f is mapping A to B ”. That which a function is thought of as doing is also referred to using the word “maps” as in: f maps X to Y . However, a set of functions may be called a set of maps so this word might also be used as the plural of a noun. There is no help for it. You just have to suffer with this nonsense.

The following theorem which is interesting for its own sake will be used to prove the Schroder Bernstein theorem, proved by Dedekind in 1887. The proof given here is like the version in Hewitt and Stromberg [62].

The following picture illustrates the conclusion of this theorem.

Proof:Consider the empty set, ∅⊆ X. If y ∈ Y ∖ f

, then g∅ because ∅ has no elements. Also, if A,B,C, and D are as described above, A also would have this same property that the empty set has. However, A is probably larger. Therefore, say A₀ ⊆ X satisfies P if whenever y ∈ Y ∖ f,gA₀.

A ≡ {A0 ⊆ X : A0 satisfies P }.

Let A = ∪A. If y ∈ Y ∖f

, then for each A₀ ∈A, y ∈ Y ∖f and so gA₀. Since gA₀ for all A₀ ∈A, it follows gA. Hence A satisfies P and is the largest subset of X which does so. Now define

C ≡ f (A),D ≡ Y ∖ C,B ≡ X ∖ A.

It only remains to verify that g

= B. It was just shown that g ⊆ B.

Suppose x ∈ B = X ∖A. Then A∪

does not satisfy P and so there exists y ∈ Y ∖f ⊆ D such that g ∈ A∪. But yf and so since A satisfies P, it follows gA. Hence g = x and so x ∈ g. Hence g = B. ■

Proof:Let A,B,C,D be the sets of Theorem1.2.2 and define

{ f (x)if x ∈ A h (x) ≡ − 1 g (x )if x ∈ B

Then h is the desired one to one and onto mapping. ■

Recall that the Cartesian product may be considered as the collection of choice functions.

The axiom of choice says that if X_i≠∅ for each i ∈ I, for I a set, then

∏ Xi ⁄= ∅. i∈I

Sometimes the two functions, f and g are onto but not one to one. It turns out that with the axiom of choice, a similar conclusion to the above may be obtained.

Proof: For each y ∈ Y , f⁻¹

≡≠∅. Therefore, by the axiom of choice, there exists f₀⁻¹ ∈∏ _y∈Y f⁻¹ which is the same as saying that for each y ∈ Y , f₀⁻¹ ∈ f⁻¹. Similarly, there exists g₀⁻¹ ∈ g⁻¹ for all x ∈ X. Then f₀⁻¹ is one to one because if  f₀⁻¹ = f₀⁻¹, then

( ) ( ) y1 = f f−01(y1) = f f0−1(y2) = y2.

Similarly g₀⁻¹ is one to one. Therefore, by the Schroder Bernstein theorem, there exists h : X → Y which is one to one and onto. ■

The property of being at most countable is often referred to as being countable because the question of interest is normally whether one can list all elements of the set, designating a first, second, third etc. in such a way as to give each element of the set a natural number. The possibility that a single element of the set may be counted more than once is often not important.

Proof:It is given that there exists a mapping η : ℕ → X which is onto. Define η

≡ x_i and consider X as the set . Similarly, consider Y as the set . It follows the elements of X × Y are included in the following rectangular array.

(x1,y1) (x1,y2) (x1,y3) ⋅⋅⋅ ← Those which have x1 in first slot. (x2,y1) (x2,y2) (x2,y3) ⋅⋅⋅ ← Those which have x2 in first slot. (x ,y ) (x ,y ) (x ,y ) ⋅⋅⋅ ← Those which have x in first slot.. 3. 1 3. 2 3. 3 . 3 .. .. .. ..

Follow a path through this array as follows.

(x1,y1) → (x1,y2) (x1,y3) → ↙ ↗ (x2,y1) (x2,y2) ↓ ↗ (x3,y1)

Thus the first element of X × Y is

, the second element of X × Y is , the third element of X × Y is etc. This assigns a number from ℕ to each element of X × Y. Thus X × Y is at most countable.

It remains to show the last claim. Suppose without loss of generality that X is countable. Then there exists α : ℕ → X which is one to one and onto. Let β : X × Y → ℕ be defined by β

≡ α⁻¹. Thus β is onto ℕ. By the first part there exists a function from ℕ onto X × Y .  Therefore, by Corollary 1.2.5, there exists a one to one and onto mapping from X × Y to ℕ. ■

Note that by induction, ∏ _i=1ⁿX_i is at most countable if each X_i is.

Proof:As in the preceding theorem,

X = {x ,x ,x ,⋅⋅⋅} 1 2 3

and

Y = {y ,y ,y ,⋅⋅⋅}. 1 2 3

Consider the following array consisting of X ∪ Y and path through it.

x1 → x2 x3 → ↙ ↗ y → y 1 2

Thus the first element of X ∪ Y is x₁, the second is x₂ the third is y₁ the fourth is y₂ etc.

Consider the second claim. By the first part, there is a map from ℕ onto X ×Y . Suppose without loss of generality that X is countable and α : ℕ → X is one to one and onto. Then define β

≡ 1, for all y ∈ Y ,and β ≡ α⁻¹. Thus, β maps X × Y onto ℕ and this shows there exist two onto maps, one mapping X ∪Y onto ℕ and the other mapping ℕ onto X ∪Y . Then Corollary 1.2.5 yields the conclusion. ■

Note that by induction this shows that if you have any finite set whose elements are countable sets, then the union of these is countable.