1.

2 The Language of Sets 7

1.2 The Language of Sets

. . . when we attempt to express in mathematical symbols a condition proposed in words.
First, we must understand thoroughly the condition. Second, we must be familiar with
the forms of mathematical expression. —George Polyá (1887–1985)

Use of the word set as a formal mathematical term was introduced in 1879 by Georg
Cantor (1845–1918). For most mathematical purposes we can think of a set intuitively, as

Cantor did, simply as a collection of elements. For instance, if C is the set of all countries
that are currently in the United Nations, then the United States is an element of C, and if
I is the set of all integers from 1 to 100, then the number 57 is an element of I .

• Notation

If S is a set, the notation x ∈ S means that x is an element of S. The notation x ∈ /S

means that x is not an element of S. A set may be specified using the set-roster
notation by writing all of its elements between braces. For example, {1, 2, 3} denotes
the set whose elements are 1, 2, and 3. A variation of the notation is sometimes used
to describe a very large set, as when we write {1, 2, 3, . . . , 100} to refer to the set
of all integers from 1 to 100. A similar notation can also describe an infinite set, as
when we write {1, 2, 3, . . .} to refer to the set of all positive integers. (The symbol
. . . is called an ellipsis and is read “and so forth.”)

The axiom of extension says that a set is completely determined by what its elements
are—not the order in which they might be listed or the fact that some elements might be
listed more than once.

Example 1.2.1 Using the Set-Roster Notation

a. Let A = {1, 2, 3}, B = {3, 1, 2}, and C = {1, 1, 2, 3, 3, 3}. What are the elements of
A, B, and C? How are A, B, and C related?
b. Is {0} = 0?
c. How many elements are in the set {1, {1}}?
d. For each nonnegative integer n, let Un = {n, −n}. Find U1 , U2 , and U0 .

Solution
a. A, B, and C have exactly the same three elements: 1, 2, and 3. Therefore, A, B, and
C are simply different ways to represent the same set.
b. {0}  = 0 because {0} is a set with one element, namely 0, whereas 0 is just the symbol
that represents the number zero.
c. The set {1, {1}} has two elements: 1 and the set whose only element is 1.
d. U1 = {1, −1}, U2 = {2, −2}, U0 = {0, −0} = {0, 0} = {0}.

Certain sets of numbers are so frequently referred to that they are given special
symbolic names. These are summarized in the table on the next page.
8 Chapter 1 Speaking Mathematically

Symbol Set
R set of all real numbers
Note The Z is the first
Z set of all integers
letter of the German word
for integers, Zahlen. It Q set of all rational numbers, or quotients of integers
stands for the set of all
integers and should not be
used as a shorthand for
the word integer. Addition of a superscript + or − or the letters nonneg indicates that only the positive
or negative or nonnegative elements of the set, respectively, are to be included. Thus
R+ denotes the set of positive real numbers, and Znonneg refers to the set of nonnegative
integers: 0, 1, 2, 3, 4, and so forth. Some authors refer to the set of nonnegative integers
as the set of natural numbers and denote it as N. Other authors call only the positive
integers natural numbers. To prevent confusion, we simply avoid using the phrase natural
numbers in this book.
The set of real numbers is usually pictured as the set of all points on a line, as shown
below. The number 0 corresponds to a middle point, called the origin. A unit of dis-
tance is marked off, and each point to the right of the origin corresponds to a positive
real number found by computing its distance from the origin. Each point to the left of
the origin corresponds to a negative real number, which is denoted by computing its dis-
tance from the origin and putting a minus sign in front of the resulting number. The set
of real numbers is therefore divided into three parts: the set of positive real numbers, the
set of negative real numbers, and the number 0. Note that 0 is neither positive nor neg-
ative Labels are given for a few real numbers corresponding to points on the line shown
below.

–3 –2 –1 0 1 2 3
2.6 13
–5 –√3 –0.8 1
√2
2 3 4

The real number line is called continuous because it is imagined to have no holes.
The set of integers corresponds to a collection of points located at fixed intervals along
the real number line. Thus every integer is a real number, and because the integers are
all separated from each other, the set of integers is called discrete. The name discrete
mathematics comes from the distinction between continuous and discrete mathematical
objects.
Another way to specify a set uses what is called the set-builder notation.
Note We read the
left-hand brace as “the set • Set-Builder Notation
of all” and the vertical
line as “such that.” In all Let S denote a set and let P(x) be a property that elements of S may or may not
other mathematical satisfy. We may define a new set to be the set of all elements x in S such that P(x)
contexts, however, we do is true. We denote this set as follows:
not use a vertical line to
denote the words “such {x ∈ S | P(x)}
that”; we abbreviate "
“such that” as “s. t.” or the set of all such that
“s. th.” or “ ·  · .”

Occasionally we will write {x | P(x)} without being specific about where the ele-
ment x comes from. It turns out that unrestricted use of this notation can lead to genuine
contradictions in set theory. We will discuss one of these in Section 6.4 and will be careful
to use this notation purely as a convenience in cases where the set S could be specified if
necessary.
 1.2 The Language of Sets 9

Example 1.2.2 Using the Set-Builder Notation

Given that R denotes the set of all real numbers, Z the set of all integers, and Z+ the set
of all positive integers, describe each of the following sets.
a. {x ∈ R | −2 < x < 5}
b. {x ∈ Z | −2 < x < 5}
c. {x ∈ Z+ | −2 < x < 5}

Solution
a. {x ∈ R | −2 < x < 5} is the open interval of real numbers (strictly) between −2 and
5. It is pictured as follows:

–3 –2 –1 0 1 2 3 4 5 6 7 8

b. {x ∈ Z | −2 < x < 5} is the set of all integers (strictly) between −2 and 5. It is equal
to the set {−1, 0, 1, 2, 3, 4}.
c. Since all the integers in Z+ are positive, {x ∈ Z+ | −2 < x < 5} = {1, 2, 3, 4}. ■

Subsets
A basic relation between sets is that of subset.

• Definition
If A and B are sets, then A is called a subset of B, written A ⊆ B, if, and only if,
every element of A is also an element of B.
Symbolically:
A⊆B means that For all elements x, if x ∈ A then x ∈ B.
The phrases A is contained in B and B contains A are alternative ways of saying that
A is a subset of B.

It follows from the definition of subset that for a set A not to be a subset of a set B
means that there is at least one element of A that is not an element of B.
Symbolically:

AB means that There is at least one element x such that x ∈ A and x ∈
/ B.

• Definition
Let A and B be sets. A is a proper subset of B if, and only if, every element of A is
in B but there is at least one element of B that is not in A.
10 Chapter 1 Speaking Mathematically

Example 1.2.3 Subsets

Let A = Z+, B = {n ∈ Z | 0 ≤ n ≤ 100}, and C = {100, 200, 300, 400, 500}. Evaluate
the truth and falsity of each of the following statements.
a. B⊆A
b. C is a proper subset of A
c. C and B have at least one element in common
d. C⊆B e. C ⊆ C

Solution
a. False. Zero is not a positive integer. Thus zero is in B but zero is not in A, and so
B  A.
b. True. Each element in C is a positive integer and, hence, is in A, but there are elements
in A that are not in C. For instance, 1 is in A and not in C.
c. True. For example, 100 is in both C and B.
d. False. For example, 200 is in C but not in B.
e. True. Every element in C is in C. In general, the definition of subset implies that all
sets are subsets of themselves.

Example 1.2.4 Distinction between ∈ and ⊆

Which of the following are true statements?
a. 2 ∈ {1, 2, 3} b. {2} ∈ {1, 2, 3} c. 2 ⊆ {1, 2, 3}
d. {2} ⊆ {1, 2, 3} e. {2} ⊆ {{1}, {2}} f. {2} ∈ {{1}, {2}}

Solution Only (a), (d), and (f) are true.

For (b) to be true, the set {1, 2, 3} would have to contain the element {2}. But the only
elements of {1, 2, 3} are 1, 2, and 3, and 2 is not equal to {2}. Hence (b) is false.
For (c) to be true, the number 2 would have to be a set and every element in the set 2
would have to be an element of {1, 2, 3}. This is not the case, so (c) is false.
For (e) to be true, every element in the set containing only the number 2 would have
to be an element of the set whose elements are {1} and {2}. But 2 is not equal to either
{1} or {2}, and so (e) is false. ■

Cartesian Products
With the introduction of Georg Cantor’s set theory in the late nineteenth century, it began
to seem possible to put mathematics on a firm logical foundation by developing all of
its various branches from set theory and logic alone. A major stumbling block was
how to use sets to define an ordered pair because the definition of a set is unaffected
Problemy monthly, July 1959

by the order in which its elements are listed. For example, {a, b} and {b, a} represent
the same set, whereas in an ordered pair we want to be able to indicate which element
comes first.
In 1914 crucial breakthroughs were made by Norbert Wiener (1894–1964), a young
American who had recently received his Ph.D. from Harvard and the German mathe-
matician Felix Hausdorff (1868–1942). Both gave definitions showing that an ordered
Kazimierz Kuratowski pair can be defined as a certain type of set, but both definitions were somewhat awkward.
(1896–1980) Finally, in 1921, the Polish mathematician Kazimierz Kuratowski (1896–1980) published
 1.2 The Language of Sets 11

the following definition, which has since become standard. It says that an ordered pair is
a set of the form
{{a}, {a, b}}.

This set has elements, {a} and {a, b}. If a = b, then the two sets are distinct and a is
in both sets whereas b is not. This allows us to distinguish between a and b and say
that a is the first element of the ordered pair and b is the second element of the pair.
If a = b, then we can simply say that a is both the first and the second element of
the pair. In this case the set that defines the ordered pair becomes {{a}, {a, a}}, which
equals {{a}}.
However, it was only long after ordered pairs had been used extensively in mathemat-
ics that mathematicians realized that it was possible to define them entirely in terms of
sets, and, in any case, the set notation would be cumbersome to use on a regular basis.
The usual notation for ordered pairs refers to {{a}, {a, b}} more simply as (a, b).

• Notation
Given elements a and b, the symbol (a, b) denotes the ordered pair consisting of a
and b together with the specification that a is the first element of the pair and b is the
second element. Two ordered pairs (a, b) and (c, d) are equal if, and only if, a = c
and b = d. Symbolically:
(a, b) = (c, d) means that a = c and b = d.

Example 1.2.5 Ordered Pairs

a. Is (1, 2) = (2, 1)?
  √ 
5
b. Is 3, 10 = 9, 12 ?

c. What is the first element of (1, 1)?

Solution
a. No. By definition of equality of ordered pairs,
(1, 2) = (2.1) if, and only if, 1 = 2 and 2 = 1.
But 1  = 2, and so the ordered pairs are not equal.
b. Yes. By definition of equality of ordered pairs,
  √  √
5
3, 10 = 9, 12 if, and only if, 3 = 9 and 5
10
= 12 .

Because these equations are both true, the ordered pairs are equal.
c. In the ordered pair (1, 1), the first and the second elements are both 1.

• Definition
Given sets A and B, the Cartesian product of A and B, denoted A × B and read
“A cross B,” is the set of all ordered pairs (a, b), where a is in A and b is in B.
Symbolically:
A × B = {(a, b) | a ∈ A and b ∈ B} .
12 Chapter 1 Speaking Mathematically

Example 1.2.6 Cartesian Products

Let A = {1, 2, 3} and B = {u, v}.
a. Find A × B
b. Find B × A
c. Find B × B
d. How many elements are in A × B, B × A, and B × B?
e. Let R denote the set of all real numbers. Describe R × R.
Solution
a. A × B = {(1, u), (2, u), (3, u), (1, v), (2, v), (3, v)}
b. B × A = {(u, 1), (u, 2), (u, 3), (v, 1), (v, 2), (v, 3)}
c. B × B = {(u, u), (u, v), (v, u), (v, v)}
Note This is why it d. A × B has six elements. Note that this is the number of elements in A times the num-
makes sense to call a ber of elements in B. B × A has six elements, the number of elements in B times
Cartesian product a the number of elements in A. B × B has four elements, the number of elements in B
product!
times the number of elements in B.
e. R × R is the set of all ordered pairs (x, y) where both x and y are real numbers. If
horizontal and vertical axes are drawn on a plane and a unit length is marked off, then
each ordered pair in R × R corresponds to a unique point in the plane, with the first
and second elements of the pair indicating, respectively, the horizontal and vertical
positions of the point. The term Cartesian plane is often used to refer to a plane with
this coordinate system, as illustrated in Figure 1.2.1.

y
3
(–3, 2)
2

1 (2, 1)

–4 –3 –2 –1 1 2 3 4 x
–1

(–2, –2) –2 (1, –2)

–3

Figure 1.2.1: A Cartesian Plane