# Set Theory

We will define a "set" to be an unordered group of objects with no duplicates. Note that the objects in the sets can themselves be sets. If a set has a finite number of objects, we can describe the set by enumerating all of the objects in it. For example, the set containing the positive integers from 1 to 5 is

{1, 2, 3, 4, 5}.
If on the other hand we wish to describe an infinite set, such as the set of even positive integers, we use what is called "set builder notation":
{x : x > 0 and x / 2 has no remainder}
This is read verbally as "the set of all x such that x is greater than 0 and x divided by 2 has a zero remainder" (where the colon ":" is read "such that").
As is always the case for standard notation which is not available on keyboards, we will sometimes denote the empty set by the numeral 0; when confusion might arise, we will use {} instead. The universal set is denoted by the capital letter U.

Two sets are equivalent if they have exactly the same objects in them. For example,

{a, b, c, d} and {c, a, d, b}
are equivalent, while
{a, b, c, d} and {{a, b}, c, d}
are not since the former set is a set of four objects, while the latter set is a set with only three objects, one of which itself is a set. It is important to note that two sets which do not have the same number of objects cannot be equivalent. Two sets are "disjoint" if they have no objects in common.
a ∈ {a, b, c}
This is read "a is a member of the set {a, b, c}" or "a is an element of the set {a, b, c}".

A "proper subset" of a set A is simply a set which contains some but not all of the objects in A. Proper subsets are denoted using the symbol

For example, the set {a, b} is a proper subset of the set {a, b, c}:
An "improper subset" is a subset which can be equal to the original set; it is notated by the symbol
which can be interpreted as "is a proper subset or is equal to".

Note that the empty set is a member of the universal set; it is also a subset of the universal set. In fact, the empty set is a subset of every set.

The rectangle "framing" the picture denotes the universal set; all things not in A, B or C are in the area surrounding them inside the frame. We will learn how to use Venn Diagrams below.

### Set Operations

There are three fundamental operations performed on sets: set union, set intersection and set complement.
but we will instead use "+" for the usual reasons. If
A = {a, b, c} and B = {b, c, d}
then
A + B = {a, b, c, d}
but we will use the symbol "&" instead (which will help remind us that set intersection is like a logical AND). If
A = {a, b, c} and B = {b, c, d}
then
A & B = {b, c}
Ac.

The following Venn Diagram illustrates the elementary set operations:

Here,
• A + B is the total of the white areas containing the letters A and B, together with the red, yellow, green and blue areas
• A & B is the red area plus the yellow area
• B + C is the total of the white areas containing the letters B and C, together with the red, yellow, green and blue areas
• B & C is the yellow area plus the green area
• A + C is the total of the white areas containing the letters A and C, together with the red, yellow, green and blue areas
• A & C is the yellow area plus the blue area
• A + B + C is everything except the magenta area
• A & B & C is the yellow area
• Ac is the total of the white areas containing the letters B and C, together with the green area and the magenta area
• Bc is the total of the white areas containing the letters A and C, together with the blue area and the magenta area
• Cc is the total of the white areas containing the letters A and B, together with the red area and the magenta area
• (A + B)c is the total of the white area containing the letter C and the magenta area
• (B + C)c is the total of the white area containing the letter A and the magenta area
• (A + C)c is the total of the white area containing the letter B and the magenta area
• (A + B + C)c is the magenta area
• (A & B)c is everything except the red and yellow areas
• (B & C)c is everything except the yellow and green areas
• (A & C)c is everything except the yellow and blue areas
• (A & B & C)c is everything except the yellow area
• A & B & Cc is the red area
• B & C & Ac is the green area
• A & C & Bc is the blue area
and so on.

Suppose that certain types of people in a given population are assigned to the sets A, B and C. For instance, set A could be the set of males in the population, set B could be the set of people under the age of 21 and set C could be the set of people who drink beer:

1. What do each of the eight regions in the above Venn diagram represent?
2. Why were none of the sets used for females, people of age 21 or older, or for those who do not drink beer?

### Set Theory is a Boolean Algebra

Set theory is
isomorphic to Boolean Algebra, as we can see using the follow substitutions:
• set union becomes the Boolean sum
• set intersection becomes the Boolean product
• set complement becomes the Boolean complement
• the universal set becomes the Boolean value 1
• the empty set becomes the Boolean value 0
The following table illustrates all of the Boolean properties and axioms as applied to set theory:
 Set Theory Boolean Algebra Identities A + 0 = A a + 0 = a A & U = A a * 1 = a Boundedness A + U = U a + 1 = 1 A & 0 = 0 a * 0 = 0 Commutative A & B = B & A a * b = b * a A + B = B + A a + b = b + a Associative (A + B) + C = A + (B + C) (a + b) + c = a + (b + c) (A & B) & C = A & (B & C) (a * b) * c = a * (b * c) Distributive A + (B & C) = (A + B) & (A + C) a + (b * c) = (a + b) * (a + c) A & (B + C) = (A & B) + (A & C) a * (b + c) = (a * b) + (a * c) Complement Laws A + Ac = U a + a' = 1 A & Ac = 0 a * a' = 0 Uniqueness of Complement A + B = U, A & B = 0 → B = Ac a + x = 1, a * x = 0 → x = a' Involution (Ac)c = A (a')' = a 0c = U 0' = 1 Uc = 0 1' = 0 Idempotent A + A = A a + a = a A & A = A a * a = a Absorption A + (A & B) = A a + (a * b) = a A & (A + B) = A a * (a + b) = a DeMorgan's (A + B)c = Ac & Bc (a + b)' = a' * b' (A & B)c = Ac + Bc (a * b)' = a' + b'
We can represent these using Venn diagrams, as shown by our depiction of the first distributive property:

A + (B & C) is the sum of the yellow and red areas, while (A + B) & (A + C) is the cyan (light blue) area (cyan is the sum of green and blue in the RGB, or Red-Green-Blue, color model).

and by our depiction of the second DeMorgan's Law:

(A & B)c is the white area on the left, while Ac + Bc is everything except the white area on the right.

It is interesting to note that the regions in a Venn diagram correspond to the terms in a Boolean sum of products expression. In the colored graph below, the colored areas have the following Boolean equivalences:

The universal set corresponds of course to the sum of all eight terms, which equals 1. The empty set corresponds to Boolean 0, as we mentioned above.

### Other Set Operations

Another set operation is set difference, denoted as
A - B = { x : x ∈ A and ~(x ∈ B) }
(read "all x such that x is an element of the set A but x is not an element of the set B"). For instance, if
A = {a, b, c} and B = {b, c, d}
then
A - B = {a}
A x B = { {a , b} : a ∈ A and b ∈ B )
This is read as "the set of all pairs {a, b} such that a is an element of the set A and b is an element of the set B". As an example of a product of sets, if the set A = {Tom, Dick, Harry} and the set B = {Mary, Jill} then A x B is the set of all possible couples:
A x B = {{Tom, Mary}, {Tom, Jill}, {Dick, Mary}, {Dick, Jill}, {Harry, Mary}, {Harry, Jill}}
The set difference operation and the Cartesian Product, along with unions and intersections, are used extensively in relational databases. For instance, a database for a matchmaking company might categorize their clients into sets of males and females who enjoy the same types of entertainment
Mfilm, Ffilm, Mjazz, Fjazz
For a given female client who is a film lover but who hates jazz, the set difference
Mfilm - Mjazz
would provide a list of possible matches, while for a male who likes both, the set union
Ffilm + Fjazz
would be possibilities. For the very picky male client who demands both, the set intersection
Ffilm & Fjazz
would be more appropriate.