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.
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 X_{i} be a set for each i ∈ I. f is a choice function written as

if f
The axiom of choice says that if X_{i}≠∅ 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 g_{0}^{−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 β
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 x_{1}, the second is x_{2} the third is y_{1} the fourth is y_{2} 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.