2.2. THE SCHRODER BERNSTEIN THEOREM 51

is contained in some universal set, U . Then

∪{

AC : A ∈S}= (∩{A : A ∈S })C

and∩{

AC : A ∈S}= (∪{A : A ∈S })C .

These laws follow directly from the definitions. Also following directly from the definitionsare:

Let S be a set of sets then

B∪∪{A : A ∈S }= ∪{B∪A : A ∈S } .

and: Let S be a set of sets show

B∩∪{A : A ∈S }= ∪{B∩A : A ∈S } .

Unfortunately, there is no single universal set which can be used for all sets. Here iswhy: Suppose there were. Call it S. Then you could consider A the set of all elements ofS which are not elements of themselves, this from the axiom of specification. If A is anelement of itself, then it fails to qualify for inclusion in A. Therefore, it must not be anelement of itself. However, if this is so, it qualifies for inclusion in A so it is an element ofitself and so this can’t be true either. Thus the most basic of conditions you could imagine,that of being an element of, is meaningless and so allowing such a set causes the wholetheory to be meaningless. The solution is to not allow a universal set. As mentioned byHalmos in Naive set theory, “Nothing contains everything”. Always beware of statementsinvolving quantifiers wherever they occur, even this one. This little observation describedabove is due to Bertrand Russell and is called Russell’s paradox.

2.2 The Schroder Bernstein TheoremIt is very important to be able to compare the size of sets in a rational way. The most usefultheorem in this context is the Schroder Bernstein theorem which is the main result to bepresented in this section. The Cartesian product is discussed above. The next definitionreviews this and defines the concept of a function.

Definition 2.2.1 Let X and Y be sets.

X×Y ≡ {(x,y) : x ∈ X and y ∈ Y}

A relation is defined to be a subset of X ×Y . A function f , also called a mapping, is arelation which has the property that if (x,y) and (x,y1) are both elements of the f , theny = y1. The domain of f is defined as

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

written as f : D( f )→ Y . Another notation which is used is the following

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

This is called the inverse image.