2.2. THE SCHRODER BERNSTEIN THEOREM 31

that there are symbols for them. The symbol ∀ is read as “for all” or “for every” and thesymbol ∃ is read as “there exists”. Thus ∀∀∃∃ could mean for every upside down A thereexists a backwards E.

DeMorgan’s laws are very useful in mathematics. Let S be a set of sets each of whichis 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.

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 .