2.2. THE SCHRODER BERNSTEIN THEOREM 53

Proof:Let A,B,C,D be the sets of Theorem2.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 2.2.4 Let I be a set and let Xi be a set for each i ∈ I. f is a choicefunction 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 with

the axiom of choice, a similar conclusion to the above may be obtained.

Corollary 2.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. ■

Definition 2.2.6 A set S, is finite if there exists a natural number n and a map θ

which maps {1, · · · ,n} one to one and onto S. S is infinite if it is not finite. A set S, is calledcountable if there exists a map θ mapping N one to one and onto S.(When θ maps a set Ato a set B, this will be written as θ : A→ B in the future.) Here N≡ {1,2, · · ·}, the naturalnumbers. S is at most countable if there exists a map θ : N→S which is onto.

The property of being at most countable is often referred to as being countable becausethe question of interest is normally whether one can list all elements of the set, designatinga 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 notimportant.

Theorem 2.2.7 If X and Y are both at most countable, then X ×Y is also at mostcountable. If either X or Y is countable, then X×Y is also countable.

Proof: It is given that there exists a mapping η :N→ X which is onto. Define η (i)≡ xiand consider X as the set {x1,x2,x3, · · ·}. Similarly, consider Y as the set {y1,y2,y3, · · ·}. Itfollows 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.(x3,y1) (x3,y2) (x3,y3) · · · ← Those which have x3 in first slot.

......

......

.