3.2. THE SCHRODER BERNSTEIN THEOREM 43

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 A is not an element of itself, it qualifies for inclusion in A soit is an element of itself and so this can’t be true either. Thus the most basic of conditionsyou could imagine, that of being an element of, is meaningless and so allowing such aset causes the whole theory to be meaningless. The solution is to not allow a universalset. As mentioned by Halmos in Naive set theory, “Nothing contains everything”. Alwaysbeware of statements involving quantifiers wherever they occur, even this one. This littleobservation described above is due to Bertrand Russell and is called Russell’s paradox.

Example 3.1.6 Various religions, including my own, use the word “omnipotent” as anattribute of god. It “means” god can do all things. Isn’t there a universal quantifier withno universal set specified? Incidentally, when speaking to religious people, it is often bestnot to call attention to this fact so they won’t think you are an atheist like Russell. Manyof the same people who believe in an “omnipotent” god are concerned with the problem ofevil (theodicy). Why does god allow evil, suffering, and sorrow? This leads to: Why doesan omnipotent god allow these things? Is god even “good”? I have heard much agonizingover the latter question in my life, but never any consideration whether it makes sense.

Theodicy has concerned intelligent people since the time of Jeremiah. See Chapter 12of Jeremiah for example, and the profound discussion in the book of Job. However, linkingtheodicy to illogical words only makes it even more difficult and challenges the existence ofGod for those who don’t realize that the omni words don’t make good sense. It only takesone of these to make their god’s existence meaningless, but religious people usually insiston saddling god with several of them. If they knew about Russell’s paradox it would help.

3.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 abstract notion of a function.

Definition 3.2.1 Let X, Y be sets. X ×Y ≡ {(x,y) : x ∈ X and y ∈ Y} . A relation isdefined to be a subset of X×Y . A function f , also called a mapping, is a relation which has