Sets

Submitted by Hermit Barber on Tue, 2011-12-20 12:10

Source: http://www.ucblueash.edu/koehler/comath/26.html

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

A^c.

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
A^c is the total of the white areas containing the letters B and C, together with the green area and the magenta area
B^c is the total of the white areas containing the letters A and C, together with the blue area and the magenta area
C^c 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 & C^c is the red area
B & C & A^c is the green area
A & C & B^c is the blue area

and so on.

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 + A^c = U	a + a' = 1
A & A^c = 0	a * a' = 0
Uniqueness of Complement	A + B = U, A & B = 0 -> B = A^c	a + x = 1, a * x = 0 -> x = a'
Involution	(A^c)^c = A	(a')' = a
0^c = U	0' = 1
U^c = 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 = A^c & B^c	(a + b)' = a' * b'
(A & B)^c = A^c + B^c	(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 A^c + B^c 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: