3.2. THE SCHRODER BERNSTEIN THEOREM 45

Let A = ∪A . If y ∈Y \ f (A), then for each A0 ∈A , y ∈Y \ f (A0) and so g(y) /∈ A0. Sinceg(y) /∈ A0 for all A0 ∈A , it follows g(y) /∈ A. Hence A satisfies P and is the largest subsetof X which does so. Now define

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

It only remains to verify that g(D) = B. It was just shown that g(D)⊆ B.Suppose x ∈ B = X \A. Then A∪{x} does not satisfy P because it is too large, and so

there exists y ∈ Y \ f (A∪{x})⊆ D such that g(y) ∈ A∪{x} . But y /∈ f (A) and so since Asatisfies P , it follows g(y) /∈ A. Hence g(y) = x and so x ∈ g(D). Hence g(D) = B.

Theorem 3.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 Theorem 3.2.2 and define

h(x)≡{

f (x) if x ∈ Ag−1 (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 func-

tions.

Definition 3.2.4 Let I be a set and let Xi be a nonempty set for each i ∈ I. f is achoice function written as

f ∈∏i∈I

Xi

if f (i) ∈ Xi for each i ∈ I. The axiom of choice says that if Xi ̸= /0 for each i ∈ I, for I a set,then

∏i∈I

Xi ̸= /0.

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

Corollary 3.2.5 If f : X → Y is onto and g : Y → X is onto, then there exists h : X → Ywhich is one to one and onto.

Proof: For each y ∈ Y , f−1 (y) ≡ {x ∈ X : f (x) = y} ̸= /0. Therefore, by the axiom ofchoice, there exists f−1

0 ∈ ∏y∈Y f−1 (y) which is the same as saying that for each y ∈ Y ,f−10 (y) ∈ f−1 (y). Similarly, there exists g−1

0 (x) ∈ g−1 (x) for all x ∈ X . Then f−10 is one to

one because if f−10 (y1) = f−1

0 (y2), then

y1 = f(

f−10 (y1)

)= f

(f−10 (y2)

)= y2.

Similarly g−10 is one to one. Therefore, by the Schroder Bernstein theorem, there exists

h : X → Y which is one to one and onto.We have already made reference to finite sets in the pigeon hole principle. The follow-

ing is just a more formal definition of what is meant by a finite set and this is generalizedto what is meant by a countable set.