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.
Definition 1.2.1 Let X and Y be sets.
|
A relation is defined to be a subset of X ×Y . A function f, also called a mapping, is a relation which has the property that if
|
written as f : D
|
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
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].
Theorem 1.2.2 Let f : X → Y and g : Y → X be two functions. Then there exist sets A,B,C,D, such that
|
|
The following picture illustrates the conclusion of this theorem.
Proof:Consider the empty set, ∅⊆ X. If y ∈ Y ∖ f
|
Let A = ∪A. If y ∈ Y ∖f
|
It only remains to verify that g
Suppose x ∈ B = X ∖A. Then A∪
Theorem 1.2.3 (Schroder Bernstein) If f : X → Y and g : Y → X are one to one, then there exists h : X → Y which is one to one and onto.
Proof:Let A,B,C,D be the sets of Theorem1.2.2 and define
|
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.
Definition 1.2.4 Let I be a set and let Xi be a set for each i ∈ I. f is a choice function written as
|
if f
The axiom of choice says that if Xi≠∅ for each i ∈ I, for I a set, then
|
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.
Corollary 1.2.5 If f : X → Y is onto and g : Y → X is onto, then there exists h : X → Y which is one to one and onto.
Proof: For each y ∈ Y , f−1
|
Similarly g0−1 is one to one. Therefore, by the Schroder Bernstein theorem, there exists h : X → Y which is one to one and onto. ■
Definition 1.2.6 A set S, is finite if there exists a natural number n and a map θ which maps
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.
Theorem 1.2.7 If X and Y are both at most countable, then X × Y is also at most countable. If either X or Y is countable, then X × Y is also countable.
Proof:It is given that there exists a mapping η : ℕ → X which is onto. Define η
|
Follow a path through this array as follows.
|
Thus the first element of X × Y is
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 β
Note that by induction, ∏ i=1nXi is at most countable if each Xi is.
Theorem 1.2.8 If X and Y are at most countable, then X ∪ Y is at most countable. If either X or Y are countable, then X ∪ Y is countable.
Proof:As in the preceding theorem,
|
and
|
Consider the following array consisting of X ∪ Y and path through it.
|
Thus the first element of X ∪ Y is x1, the second is x2 the third is y1 the fourth is y2 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 β
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.