42 CHAPTER 3. SET THEORY

the elements in each of the sets in the collection. Of course this is also open to furtherconsideration. What is a collection? Maybe it would be better to say “set of sets” or, givena set whose elements are sets there exists a set whose elements consist of exactly thosethings which are elements of at least one of these sets. If S is such a set whose elementsare sets,

∪{A : A ∈S } or ∪S

signifies this union.Something is in the Cartesian product of a set or “family” of sets if it consists of a single

thing taken from each set in the family. Thus (1,2,3) ∈ {1,4, .2}×{1,2,7}×{4,3,7,9}because it consists of exactly one element from each of the sets which are separated by ×.Also, this is the notation for the Cartesian product of finitely many sets. If S is a set whoseelements are sets, ∏A∈S A signifies the Cartesian product.

The Cartesian product is the set of choice functions, a choice function being a functionwhich selects exactly one element of each set of S . Functions will be described preciselysoon. The idea is that there is something, which will produce a set consisting of exactly oneelement of each set of S . You may think the axiom of choice, stating that the Cartesianproduct of a nonempty family of nonempty sets is nonempty, is innocuous but there was atime when many mathematicians were ready to throw it out because it implies things whichare very hard to believe, things which never happen without the axiom of choice.

A is a subset of B, written A⊆ B, if every element of A is also an element of B. This canalso be written as B⊇ A. A is a proper subset of B, written A⊂ B or B⊃ A if A is a subsetof B but A is not equal to B,A ̸= B. However, this is not entirely consistent. Sometimespeople write A⊂ B when they mean A⊆ B. A∩B denotes the intersection of the two sets,A and B and it means the set of elements of A which are also elements of B. The axiomof specification shows this is a set. The empty set is the set which has no elements in it,denoted as /0. A∪B denotes the union of the two sets, A and B and it means the set of allelements which are in either of the sets. It is a set because of the axiom of unions.

The complement of a set, (the set of things which are not in the given set ) must betaken with respect to a given set called the universal set, a set which contains the onewhose complement is being taken. Thus, the complement of A, denoted as AC ( or moreprecisely as X \A) is a set obtained from using the axiom of specification to write

AC ≡ {x ∈ X : x /∈ A}

The symbol /∈ means: “is not an element of”. Note the axiom of specification takes placerelative to a given set. Without this universal set, it makes no sense to use the axiom ofspecification to obtain the complement.

Words such as “all” or “there exists” are called quantifiers and they must be understoodrelative to some given set. For example, the set of all integers larger than 3. Or thereexists an integer larger than 7. Such statements have to do with a given set, in this case theintegers. Failure to have a reference set when quantifiers are used turns out to be illogicaleven though such usage may be grammatically correct. Quantifiers are used often enoughthat 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