Page 139 - Discrete Mathematics and Its Applications

118 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

THE EMPTY SET There is a special set that has no elements. This set is called the empty set,
or null set, and is denoted by ∅. The empty set can also be denoted by {} (that is, we represent
the empty set with a pair of braces that encloses all the elements in this set). Often, a set of
elements with certain properties turns out to be the null set. For instance, the set of all positive
integers that are greater than their squares is the null set.
A set with one element is called a singleton set. A common error is to confuse the empty
{∅} has one more
set ∅ with the set {∅}, which is a singleton set. The single element of the set {∅} is the empty set
element than ∅.
itself! A useful analogy for remembering this difference is to think of folders in a computer file
system. The empty set can be thought of as an empty folder and the set consisting of just the
empty set can be thought of as a folder with exactly one folder inside, namely, the empty folder.

NAIVE SET THEORY Note that the term object has been used in the definition of a set,
Definition 1, without specifying what an object is. This description of a set as a collection
of objects, based on the intuitive notion of an object, was first stated in 1895 by the German
mathematician Georg Cantor. The theory that results from this intuitive definition of a set, and
the use of the intuitive notion that for any property whatever, there is a set consisting of exactly
the objects with this property, leads to paradoxes, or logical inconsistencies. This was shown
by the English philosopher Bertrand Russell in 1902 (see Exercise 46 for a description of one of
these paradoxes). These logical inconsistencies can be avoided by building set theory beginning
with axioms. However, we will use Cantor’s original version of set theory, known as naive set
theory, in this book because all sets considered in this book can be treated consistently using
Cantor’s original theory. Students will find familiarity with naive set theory helpful if they go on
to learn about axiomatic set theory. They will also find the development of axiomatic set theory
much more abstract than the material in this text. We refer the interested reader to [Su72] to
learn more about axiomatic set theory.

Venn Diagrams

Sets can be represented graphically using Venn diagrams, named after the English mathemati-
cian John Venn, who introduced their use in 1881. In Venn diagrams the universal set U, which
contains all the objects under consideration, is represented by a rectangle. (Note that the uni-
versal set varies depending on which objects are of interest.) Inside this rectangle, circles or
other geometrical figures are used to represent sets. Sometimes points are used to represent the
particular elements of the set.Venn diagrams are often used to indicate the relationships between
sets. We show how a Venn diagram can be used in Example 7.

EXAMPLE 7 Draw a Venn diagram that represents V, the set of vowels in the English alphabet.

Solution: We draw a rectangle to indicate the universal set U, which is the set of the 26 letters
of the English alphabet. Inside this rectangle we draw a circle to represent V . Inside this circle
we indicate the elements of V with points (see Figure 1). ▲

U
a

u e
V

o i

FIGURE 1 Venn Diagram for the Set of Vowels.