44 CHAPTER 3. SET THEORY

the property that if (x,y) and (x,y1) are both elements of the f , then y = y1. The domain off is defined as

D( f )≡ {x : (x,y) ∈ f} ,

written as f : D( f )→ Y and we write y = f (x). Another notation which is used is thefollowing

f−1 (y)≡ {x ∈ D( f ) : f (x) = y}

This is called the inverse image.

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, proved by Dedekind in 1887. The shortest proof I have seenis in Hewitt and Stromberg [17] and this is the version given here. There is another versionin Halmos [15].

Theorem 3.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}.