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").

There are two special sets: the "empty set" and the "universal set". The empty set (or null set) is the set which contains no objects and is denoted {}, or by the symbol

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.

Set membership is notated using the symbol ∈:

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.

Relationships between multiple sets are sometimes graphically described using Venn Diagrams. A Venn Diagram describing the relationship between three sets A, B and C always begins with the following picture:

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.

The union of two sets A and B is the set which contains all of the elements in both A and B. It is usually denoted with the symbol

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}

The intersection of two sets A and B is the set which contains only those elements which are in both A and B. It is usually denoted by the symbol

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}

The complement of a set A is all of the objects in the universal set except those in A, and is denoted

Ac.

The following Venn Diagram illustrates the elementary set operations:

Here, 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: The following table illustrates all of the Boolean properties and axioms as applied to set theory:
Set TheoryBoolean Algebra
IdentitiesA + 0 = Aa + 0 = a
A & U = Aa * 1 = a
BoundednessA + U = Ua + 1 = 1
A & 0 = 0a * 0 = 0
CommutativeA & B = B & Aa * b = b * a
A + B = B + Aa + 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)
DistributiveA + (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 LawsA + Ac = Ua + a' = 1
A & Ac = 0a * a' = 0
Uniqueness of ComplementA + B = U, A & B = 0 → B = Ac a + x = 1, a * x = 0 → x = a'
Involution(Ac)c = A(a')' = a
0c = U0' = 1
Uc = 01' = 0
IdempotentA + A = Aa + a = a
A & A = Aa * a = a
AbsorptionA + (A & B) = Aa + (a * b) = a
A & (A + B) = Aa * (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}

We can construct products of sets (sometimes called "Cartesian Products" or "cross products" or "outer products") as follows:

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.

In the next chapter, we will study yet another non-numerical branch of mathematics: Graph Theory.


Go to:Title PageTable of ContentsIndex

©2012, Kenneth R. Koehler. All Rights Reserved. This document may be freely reproduced provided that this copyright notice is included.

Please send comments or suggestions to the author.