4 CHAPTER 1. SOME PREREQUISITE TOPICS

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 thereexists h : X → Y which is one to one and onto.

Proof:Let A,B,C,D be the sets of Theorem 1.2.2 and define

h(x)≡

{f (x) if x ∈ A

g−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 choice functionwritten 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 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 θ whichmaps {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 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.