6 CHAPTER 1. BASIC NOTIONS

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 and so there exists y ∈

Y \ f (A∪{x}) ⊆ D such that g(y) ∈ A∪{x} . But y /∈ f (A) and so since A satisfies P , itfollows g(y) /∈ A. Hence g(y) = x and so x ∈ g(D). Hence g(D) = B. ■

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

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 1.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 withthe 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 → 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 1.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.