3. Notes in set theory

3.1. Notation and Terminology

Definition 3.1.1. A set is a collection of objects called elements of the set. 

Why not use the word “collection” and eliminate the word “set”, thereby having fewer words to worry about? “Collection” is a common word whose generic meaning is understood by most people. The use of the word “set” means that there is also a method to determine whether or not a particular object belongs in the set. We then say that the set is well-defined. 

For example, it is easy to decide that the number 8 is not in the set consisting of the integers 1 through 5. After all, there are only five objects to consider and it is clear that 8 is not one of them by simply checking all five.

A basic problem here is now to indicate sets on paper and verbally. As seen above, a set could be described with a phrase such as “the integers 1 through 5” and the speaker hopes that it is understood. Symbollically, we use two common methods to write sets. 

Definition 3.1.2. The roster notation is a complete or implied listing of all the elements of the set. 

So A={a,b,c,d} and  B={2,4,6,8,...,40} are examples of roster notation defining sets with 4 and 20 elements respectively. The ellipsis, “...”, is used to mean you fill in the missing elements in the obvious manner or pattern, as there are too many to actually list out on paper. 

Definition 3.1.3. The set-builder notation is used when the roster method is cumbersome or impossible. 

The set B above could be described by {x| 2 ⩽x≤40 and x is even} . The vertical bar, “|’”, is read as “such that” so this notation is read aloud as “the set of x such that x is between 2 and 40 (inclusive) and x is even.’’ (Sometimes a colon is used instead of |.) In set-builder notation, whatever comes after the bar describes the rule for determining whether or not an object is in the set. For the set {x| x is real number} the roster notation would be impossible since there are too many reals to actually list out, explicitly or implicitly.

To discuss and manipulate sets we need a short list of symbols commonly used in print. We start with five symbols summarized in the following table.

Table 3.1.4.

data={{"Symbol","Meaning", "Example","Read as:"},
{"∈","element of","x∈A","'x an element of A'or 'x in A'"},
{"⊂","subset","A⊂B","'A os a subset of B' or 'A contained in B'"},
{"⋃","union","A ⋃ B","A union B"},
{"⋂","intersection","A ⋂ B","A intersect B"},
{"'","complement","A'","A complement"}
};
makeTextTable[data]

The first symbol, ∈ , indicates membership of an object in a particular set. The negation of this, or nonmembership is often indicated by “x ∉ A” (“x is not in A”). The subset relation, A⊂B , states that every element of A is also an element of B. Logically, this would be: if x ∈ A then x∈B. The union and intersection operators form new sets by the following rules.

Set union and set intersection examples

Let A = {1,3,5,7,9} and  B = {2,3,4,5,6}.

A ⋃ B consists of the elements in A or B so  A ⋃ B = {1,2,3,4,5,6,7,9}.

A ⋂ B consists of the elements in both A and B so A ⋂ B = {3,5}.

The set A ⋃ B is defined to be { x| x ∈ A or x ∈ B } while A ⋂ B is defined to be { x| x ∈ A and x ∈ B } . Finally, the complement of a set consists of those objects that are not in the given set. This presents a minor problem. If A = { -3, π , (Sqrt[2])} then clearly I am not in A so should I be considered an element of  A’ ? Normally not, I think. Underlying a discussion or argument involving sets is usually a large set called the universal set or universe of the discourse and is commonly denoted by U. This universe may be implied or stated explicitly. Operations involving union, intersection or complement are understood to be contained in this universe. 

For example, if we were discussing real numbers (so that our universe would be the set of reals) and mentioned the set A above with 3 elements, it is understood that  A’ consists of those real numbers not in A. This conveniently excludes me from the set  A’ .

3.2. More on set operations

3.2.1. Arbitrary unions and intersections

The notions of union and intersection can be easily extended to more than two sets.

For finitely many sets, say (Subscript[A, 1]), (Subscript[A, 2]),..., (Subscript[A, 10]) we write (Subscript[A, 1]) ⋃ (Subscript[A, 2]) ⋃ ... ⋃ (Subscript[A, 10])  or (Underoverscript[ ⋃, (n=1), 10])(Subscript[A, n])  and (Subscript[A, 1]) ⋂ (Subscript[A, 2]) ⋂ ... ⋂ (Subscript[A, 10])  or (Underoverscript[ ⋂, (n=1), 10])(Subscript[A, n]). If we have a sequence of sets ((Subscript[A, n]))_(n=1)^∞ we write  (Underoverscript[ ⋃, (n=1), ∞])(Subscript[A, n]) and (Underoverscript[ ⋂, (n=1), ∞])(Subscript[A, n]). 

Perhaps the most general form of this notation is a collection of sets with subscripts in some general index set Γ, ((Subscript[A, γ])| γ ∈ Γ) . Here Γ could be finite or infinite. We then write (Underscript[ ⋃, γ∈Γ])(Subscript[A, γ]) and (Underscript[ ⋂, γ∈Γ])(Subscript[A, γ]) . So an alternate way to write (Underoverscript[ ⋂, (n=1), ∞])(Subscript[A, n]) would be (Underscript[ ⋂, n∈N])(Subscript[A, n]) where N is the set of natural numbers.

Exactly what these symbols mean is as follows.

By (Underscript[ ⋃, γ∈Γ])(Subscript[A, γ]) we mean {x| (Subscript[∃, γ∈Γ]) x ∈ (Subscript[A, γ])} and by (Underscript[ ⋂, γ∈Γ])(Subscript[A, γ])  we mean  {x| (Subscript[∀, γ∈Γ]) x ∈ (Subscript[A, γ])}.

Check that these become our original definitions of set union and intersection when the indexing set has just two elements, and then we can just call the two sets A and B. An example of a large indexing set would be the set of reals R. If  (Subscript[A, x])={(x,y)| y real} then (Underscript[ ⋃, x∈R])(Subscript[A, x]) would be the entire Cartesian plane  R x R written as a union of all vertical lines in the plane.

Some care must be taken when dealing with negations involving union and intersections. Since x∈ (Underscript[ ⋃, γ∈Γ])(Subscript[A, γ]) means there is at least one  γ so that  x ∈ (Subscript[A, γ]) , then x∉ (Underscript[ ⋃, γ∈Γ])(Subscript[A, γ]) means x is not in any (Subscript[A, γ]). (Logically we have ¬ ((Subscript[∃, γ∈Γ])x∈(Subscript[A, γ])) ≈ (Subscript[∀, γ∈Γ]) x ∉ (Subscript[A, γ]).) Similarly, Since  x ∈(Underscript[ ⋂, γ∈Γ])(Subscript[A, γ])  means  x∈(Subscript[A, γ]) for every γ, then x ∉(Underscript[ ⋂, γ∈Γ])(Subscript[A, γ])means there is at least one γ with x ∉ (Subscript[A, γ]) . (Logically we have ¬((Subscript[∀, γ∈Γ])x∈(Subscript[A, γ])) ≈ (Subscript[∃, γ∈Γ]) x ∉ (Subscript[A, γ]).)

3.2.2. Manipulating Unions and Intersections

Boolean Algebra

Definition 3.2.2.a.1. A Boolean algebra is a set with two binary operations, ⋃ and ⋂ , that are commutative, associative and each distributes over the other, plus a unary operation ‘ . Also required are identity elements ϕ and U for the binary operations that satisfy A ⋃ ϕ = A , A ⋂ U = A , A ⋃ A’ = U  and A ⋂ A’ = ϕ for all elements A in the set.

One interpretation of Boolean algebra is the collection of subsets of a fixed set X. We take ⋃ , ⋂ , ‘ , ϕ and U to be set union, set intersection, complementation, the empty set and the set X respectively. Equality here means the usual equality of sets.

Another interpretation is the calculus of propositions in symbolic logic. Here we take  ⋃ , ⋂ , ‘ , ϕ  and U to be disjunction, conjunction, negation, a fixed contradiction and a fixed tautology respectively. In this setting equality means logical equivalence.

It is not surprising then that we find analogous properties and rules appearing in these two areas. For example, the axiom of the distributive properties says that for sets we have A ⋃ (B ⋂ C) = (A ⋃ B) ⋂ (A ⋃ C) while p ∨ (q ∧ r) ↔( p ∨ q) ∧ (p ∨ r) is a familiar equivalence in logic.

From the axioms above one can prove DeMorgan’s Laws (in some axiom sets this is included as an axiom). The following table contains just a few rules that hold in a Boolean algebra, written in both set and logic notation. Rows 3 and 4 are DeMorgan’s Laws. Note that the two versions of these rules are identical in structure, differing only in the choice of symbols.

Table 3.2.2.a.2.

data={{"Set vesion","Logic version"},
{"A ⋃ (B ⋂ C) = (A ⋃ B) ⋂ (A ⋃ C)","p ∨ (q ∧ r) ↔( p ∨ q) ∧ (p ∨ r)"},
{"A ⋂ (B ⋃ C) = (A ⋂ B) ⋃ (A ⋂ C)","p ∧ (q ∨ r) ↔( p ∧ q) ∨ (p ∧ r)"},
{"(A ⋃ B)' = A' ⋂ B'","¬(p ∨ q)↔ ¬p ∧ ¬q"},
{"(A ⋂ B)' = A' ⋃ B'","¬(p ∧ q)↔ ¬p ∨ ¬q"},
{"A ⋃ A = A","p ∨ q ↔ p"}
};
makeTextTable[data]

The important rules (A ⋃ B)’ = A’ ⋂ B’ and (A ⋂ B)’ = A’ ⋃ B’ are known as DeMorgan’s Laws.

De Morgan’s law

Example using DeMorgan’s Law: Let A = {a,d,e,g} and B = {c,d,f,g} in the universe U = {a,b,c,d,e,f,g,h,i } To verify that  (A ⋃ B)’ = A’ ⋂ B’  find each of these two sets independently to find that they are indeed the same.

First:  (A ⋃ B)’ ={a,c,d,e,f,g}’ = {b,h,i}

Second:  A’ ⋂ B’ ={b,c,f,h,i} ⋂ {a,b,e,h,i} = {b,h,i}

As predicted, {b,h,i} = {b,h,i} !

These rules also extend to arbitrary unions and intersections as ( (Underscript[ ⋃, γ∈Γ]) (Subscript[A, γ]) ())' = (Underscript[ ⋂, γ∈Γ]) (Subscript[A, γ])' and  ( (Underscript[ ⋂, γ∈Γ]) (Subscript[A, γ]) ())' =  (Underscript[ ⋃, γ∈Γ]) (Subscript[A, γ])'

Set equality

DeMorgan’s Law:    ( (Underscript[ ⋂, γ∈Γ]) (Subscript[A, γ]) ())' =  (Underscript[ ⋃, γ∈Γ]) (Subscript[A, γ])' .

If we are given specific sets (Subscript[A, γ]) then we could probably calculate the two sets equated in DeMorgan’s Law and see that they are in fact equal. To prove this law in general we can use a technique often used to prove the equality of two sets. The idea is simply this: to prove that A=B we could show that A ⊂ B and  B ⊂ A. This works very nicely on DeMorgan’s Law as follows.

First, assume x ∈ ( (Underscript[ ⋂, γ∈Γ]) (Subscript[A, γ]) ())' . This says x ∉  ( (Underscript[ ⋂, γ∈Γ]) (Subscript[A, γ]) )  so there exists a γ with   x ∉ (Subscript[A, γ]) . Thus  x ∈ (Subscript[A, γ])' (for this particular ) and we have x ∈ (Underscript[ ⋃, γ∈Γ]) (Subscript[A, γ])' . This short argument establishes the fact that  ( (Underscript[ ⋂, γ∈Γ]) (Subscript[A, γ]) ())' ⊂ (Underscript[ ⋃, γ∈Γ]) (Subscript[A, γ])' by showing that an arbitrary element of the first set must be an element of the second.

Second, assume that x ∈ (Underscript[ ⋃, γ∈Γ]) (Subscript[A, γ])' . This says that there exists a γ with  x ∈ (Subscript[A, γ])'. Thus  x ∉ (Subscript[A, γ]) (for this particular γ ) and we have  x ∉  ( (Underscript[ ⋂, γ∈Γ]) (Subscript[A, γ]) )   so  x ∈ ((Underscript[ ⋂, γ∈Γ]) (Subscript[A, γ])())' . This establishes the fact that  ( (Underscript[ ⋂, γ∈Γ]) (Subscript[A, γ]) ())' ⊃ (Underscript[ ⋃, γ∈Γ]) (Subscript[A, γ])' .

Putting these two results together verifies DeMorgan’s Law. Note that the second argument is essentially the first argument in reverse. This is quite often the case when showing two sets are equal by this method and you can see that most of the work is done when the first argument is complete. That’s what makes this approach nice to use in many situations.

In manipulating expressions involving set operations it is often convenient to distribute one set operation over another.Specifically we have   A ⋂ (B ⋃ C) = (A ⋂ B) ⋃ (A ⋂ C) and  A ⋃ (B ⋂ C) = (A ⋃ B) ⋂ (A ⋃ C)