{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 "

{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

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

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

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 "

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.

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

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:

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

- 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

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' |

and by our depiction of the second DeMorgan's Law: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).

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:(A & B)

^{c}is the white area on the left, while A^{c}+ B^{c}is everything except the white area on the right.

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.

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

MFor a given female client who is a film lover but who hates jazz, the set difference_{film}, F_{film}, M_{jazz}, F_{jazz}

Mwould provide a list of possible matches, while for a male who likes both, the set union_{film}- M_{jazz}

Fwould be possibilities. For the very picky male client who demands both, the set intersection_{film}+ F_{jazz}

Fwould be more appropriate._{film}& F_{jazz}

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

Go to: Title Page Table of Contents Index

©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.