52 CHAPTER 2. SOME BASIC TOPICS

It is probably safe to say that most people do not think of functions as a type of relationwhich is a subset of the Cartesian product of two sets. A function is like a machine whichtakes inputs, x and makes them into a unique output, f (x). Of course, that is what theabove definition says with more precision. An ordered pair, (x,y) which is an element ofthe function or mapping has an input, x and a unique output y,denoted as f (x) while thename of the function is f . “mapping” is often a noun meaning function. However, it alsois a verb as in “ f is mapping A to B ”. That which a function is thought of as doing is alsoreferred to using the word “maps” as in: f maps X to Y . However, a set of functions maybe called a set of maps so this word might also be used as the plural of a noun. There is nohelp for it. You just have to suffer with this nonsense.

The following theorem which is interesting for its own sake will be used to prove theSchroder Bernstein theorem.

Theorem 2.2.2 Let f : X →Y and g : Y → X be two functions. Then there exist setsA,B,C,D, such that

A∪B = X , C∪D = Y, A∩B = /0, C∩D = /0,

f (A) =C, g(D) = B.

The following picture illustrates the conclusion of this theorem.

B = g(D)

A

D

C = f (A)

YX

f

g

Proof:Consider the empty set, /0 ⊆ X . If y ∈ Y \ f ( /0), then g(y) /∈ /0 because /0 hasno elements. Also, if A,B,C, and D are as described above, A also would have this sameproperty that the empty set has. However, A is probably larger. Therefore, say A0 ⊆ Xsatisfies P if whenever y ∈ Y \ f (A0) , g(y) /∈ A0.

A ≡ {A0 ⊆ X : A0 satisfies P}.

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