i∈{1,2,3}
as this takes the union of the sets Ai for i = 1, 2, 3. Likewise:
3
Ai =
Ai
i=1
i∈{1,2,3}
∞
[ Ai =
[ Ai
i=1
i∈N
∞
Ai =
Ai
i=1
i∈N
Here we are taking the union or intersection of a collection of sets Ai
©
where i is an element of some set, be it 1, 2, 3ª or N. In general, the way
this works is that we will have a collection of sets Ai for i ∈ I, where I is
the set of possible subscripts. The set I is called an index set.
It is important to realize that the set I need not even consist of integers.
(We could subscript with letters or real numbers, etc.)
Since we are
programmed to think of i as an integer, let’s make a slight notational
change: We use α, not i, to stand for an element of I. Thus we are dealing
with a collection of sets A α for α ∈ I. This leads to the following definition.
Definition 1.8
If we have a set A α for every α in some index set I, then
[ A α = ©x : x ∈ A α for at least one set A α with α ∈ Iª
α∈I
A α = ©x : x ∈ A α for every set A α with α ∈ Iª.
α∈I
26
Sets
Example 1.11
Here the sets A α will be subsets of R2. Let I = [0, 2] =
©x ∈ R : 0 ≤ x ≤ 2ª. For each number α ∈ I, let A α = ©(x, α) : x ∈ R,1 ≤ x ≤ 2ª. For
instance, given α = 1 ∈ I the set A1 = ©(x, 1) : x ∈ R, 1 ≤ x ≤ 2ª is a horizontal
line segment one unit above the x-axis and stretching between x = 1 and
p
x = 2, as shown in Figure 1.11(a). Likewise Ap
2) : x
2 = ©(x,
∈ R, 1 ≤ x ≤ 2ª is
p
a horizontal line segment
2 units above the x-axis and stretching between
x = 1 and x = 2. A few other of the A α are shown in Figure 1.11(a), but they
can’t all be drawn because there is one A α for each of the infinitely many
numbers α ∈ [0, 2]. The totality of them covers the shaded region in Figure
1.11(b), so this region is the union of all the A α. Since the shaded region
©
is the set (x, y) ∈ R2 : 1 ≤ x ≤ 2, 0 ≤ y ≤ 2ª = [1, 2] × [0, 2], it follows that
[
A α = [1,2] × [0,2].
α∈[0,2]
Likewise, since there is no point (x, y) that is in every set A α, we have
A α = ;.
α∈[0,2]
y
y
2
A2
2
Ap2
[
A
1
A
α
1
1
α∈[0,2]
A0.5
A0.25
x
x
1
2
1
2
(a)
(b)
Figure 1.11. The union of an indexed collection of sets
One final comment. Observe that A α = [1, 2] × © αª, so the above expres-
sions can be written as
[
[1, 2] × © αª = [1,2] × [0,2]
and
[1, 2] × © αª = ;.
α∈[0,2]
α∈[0,2]
Indexed Sets
27
Example 1.12
In this example our sets are indexed by R2.
For any
(a, b) ∈ R2, let P(a,b) be the following subset of R3:
P(a,b) = ©(x, y, z) ∈ R3 : ax + b y = 0ª.
In words, given a point (a, b) ∈ R2, the corresponding set P(a,b) consists of
all points (x, y, z) in R3 that satisfy the equation ax + b y = 0. From previous
math courses you will recognize this as a plane in R3, that is, P(a,b) is a
plane in R3. Moreover, since any point (0, 0, z) on the z-axis automatically
satisfies ax + b y = 0, each P(a,b) contains the z-axis.
Figure 1.12 (left) shows the set P(1,2) = ©(x, y, z) ∈ R3 : x + 2 y = 0ª. It is the
vertical plane that intersects the x y-plane at the line x + 2 y = 0.
z
P(1,2)
y
(−2,1,0)
x
Figure 1.12. The sets P(a,b) are vertical planes containing the z-axis.
For any point (a, b) ∈ R2 with (a, b) 6= (0, 0), we can visualize P(a,b) as the
vertical plane that cuts the x y-plane at the line ax + b y = 0. Figure 1.12
(right) shows a few of the P(a,b). Since any two such planes intersect
along the z-axis, and because the z-axis is a subset of every P(a,b), it is
immediately clear that
P(a,b) = ©(0,0, z) : z ∈ Rª = “the z-axis”.
(a,b)∈R2
For the union, note that any given point (a, b, c) ∈ R3 belongs to the set
P(−b,a) because (x, y, z) = (a, b, c) satisfies the equation −bx + ay = 0. (In fact,
any (a, b, c) belongs to the special set P(0,0) = R3, which is the only P(a,b) that
is not a plane.) Since any point in R3 belongs to some P(a,b) we have
[
P(a,b) = R3.
(a,b)∈R2
28
Sets
Exercises for Section 1.8
1. Suppose A1 = ©a, b, d, e, g, f ª, A2 = ©a, b, c, dª, A3 = ©b, d, aª and A4 = ©a, b, hª.
4
4
(a)
[ A
i =
(b)
Ai =
i=1
i=1
A1
=
©0,2,4,8,10,12,14,16,18,20,22,24ª,
2. Suppose
A2
=
©0,3,6,9,12,15,18,21,24ª,
A3
=
©0,4,8,12,16,20,24ª.
3
3
(a)
[ A
i =
(b)
Ai =
i=1
i=1
3. For each n ∈ N, let An = ©0,1,2,3,..., nª.
(a)
[ Ai =
(b)
Ai =
i∈N
i∈N
4. For each n ∈ N, let An = © − 2n,0,2nª.
(a)
[ Ai =
(b)
Ai =
i∈N
i∈N
5. (a)
[ [i, i + 1] =
(b)
[i, i + 1] =
i∈N
i∈N
6. (a)
[ [0, i + 1] =
(b)
[0, i + 1] =
i∈N
i∈N
7. (a)
[ R × [i, i + 1] =
(b)
R × [i, i + 1] =
i∈N
i∈N
8. (a)
[ © αª × [0,1] =
(b)
© αª × [0,1] =
α∈R
α∈R
9. (a)
[
X =
(b)
X =
X ∈P(N)
X ∈P(N)
10. (a)
[
[x, 1] × [0, x2] =
(b)
[x, 1] × [0, x2
] =
x∈[0,1]
x∈[0,1]
11.
Is
A α ⊆ [ A α always true for any collection of sets A α with index set I?
α∈I
α∈I
12.
If
A α = [ A α, what do you think can be said about the relationships between
α∈I
α∈I
the sets A α?
13.
[
If J 6= ; and J ⊆ I, does it follow that
A α ⊆ [ A α? What about
A α ⊆ A α?
α∈J
α∈I
α∈J
α∈I
14.
If J 6= ; and J ⊆ I, does it follow that
A α ⊆ A α? Explain.
α∈I
α∈J
Sets that Are Number Systems
29
1.9 Sets that Are Number Systems
In practice, the sets we tend to be most interested in often have special
properties and structures. For example, the sets Z, Q and R are familiar
number systems: Given such a set, any two of its elements can be added
(or multiplied, etc.) together to produce another element in the set. These
operations obey the familiar commutative, associative and distributive
properties that we all have dealt with for years. Such properties lead to
the standard algebraic techniques for solving equations. Even though we
are concerned with the idea of proof, we will not find it necessary to define,
prove or verify such properties and techniques; we will accept them as the
ground rules upon which our further deductions are based.
We also accept as fact the natural ordering of the elements of N, Z, Q
and R, so that (for example) the meaning of “5 < 7” is understood and does
not need to be justified or explained. Similarly, if x ≤ y and a 6= 0, we know
that ax ≤ a y or ax ≥ a y, depending on whether a is positive or negative.
Another thing that our ingrained understanding of the ordering of
numbers tells us is that any non-empty subset of N has a smallest element.
In other words, if A ⊆ N and A 6= ;, then there is an element x0 ∈ A that is
smaller than every other element of A. (To find it, start at 1, then move
in increments to 2, 3, 4, etc., until you hit a number x0 ∈ A; this is the
smallest element of A.) Similarly, given an integer b, any non-empty subset
A ⊆ ©b, b + 1, b + 2, b + 3,...ª has a smallest element. This fact is sometimes
called the well-ordering principle. There is no need to remember this
term, but do be aware that we will use this simple, intuitive idea often in
proofs, usually without a second thought.
The well-ordering principle seems innocent enough, but it actually says
something very fundamental and special about the positive integers N.
In fact, the corresponding statement about the positive real numbers
is false: The subset A = © 1 : n
n
∈ Nª of the positive reals has no smallest
element because for any x0 = 1n ∈ A that we might pick, there is always a
1
smaller element n+1 ∈ A.
One consequence of the well-ordering principle (as we will see below)
is the familiar fact that any integer a can be divided by a non-zero integer
b, resulting in a quotient q and remainder r. For example, b = 3 goes
into a = 17 q = 5 times with remainder r = 2. In symbols, 17 = 5 · 3 + 2, or
a = qb + r. This significant fact is called the division algorithm.
Fact 1.5
(The Division Algorithm) Given integers a and b with b > 0,
there exist integers q and r for which a = qb + r and 0 ≤ r < b.
30
Sets
Although there is no harm in accepting the division algorithm without
proof, note that it does follow from the well-ordering principle. Here’s how:
Given integers a, b with b > 0, form the set
A = ©a − xb : x ∈ Z, 0 ≤ a − xbª ⊆ ©0,1,2,3,...ª.
(For example, if a = 17 and b = 3 then A = ©2, 5, 8, 11, 14, 17, 20, . . . ª is the set
of positive integers obtained by adding multiples of 3 to 17. Notice that
the remainder r = 2 of 17÷3 is the smallest element of this set.) In general,
let r be the smallest element of the set A = ©a − xb : x ∈ Z, 0 ≤ a − xbª. Then
r = a − qb for some x = q ∈ Z, so a = qb + r. Moreover, 0 ≤ r < b, as follows.
The fact that r ∈ A ⊆ ©0, 1, 2, 3 . . . ª implies 0 ≤ r.
In addition, it cannot
happen that r ≥ b: If this were the case, then the non-negative number
r −b = (a− qb)−b = a−(q+1)b having form a− xb would be a smaller element
of A than r, and r was explicitly chosen as the smallest element of A.
Since it is not the case that r ≥ b, it must be that r < b. Therefore 0 ≤ r < b.
We’ve now produced a q and an r for which a = qb + r and 0 ≤ r < b.
Moving on, it is time to clarify a small issue. This chapter asserted
that all of mathematics can be described with sets. But at the same time
we maintained that some mathematical entities are not sets. (For instance,
our approach was to say that an individual number, such as 5, is not itself
a set, though it may be an element of a set.)
We have made this distinction because we need a place to stand as
we explore sets: After all, it would appear suspiciously circular to declare
that every mathematical entity is a set, and then go on to define a set as
a collection whose members are sets!
But to most mathematicians, saying “The number 5 is not a set,” is
like saying “The number 5 is not a number.”
The truth is that any number can itself be understood as a set. One
way to do this is to begin with the identification 0 = ;. Then 1 = {;} = {0},
and 2 = ©;, {;}ª = {0, 1}, and 3 = ©;, {;}, {;, {;}}ª = {0, 1, 2}.
In general the
natural number n is the set n = {0, 1, 2, . . . , n − 1} of the n numbers (which
are themselves sets) that come before it.
We will not undertake such a study here, but the elements of the
number systems Z, Q and R can all be defined in terms of sets. (Even the
operations of addition, multiplication, etc., can be defined in set-theoretic
terms.) In fact, mathematics itself can be regarded as the study of things
that can be described as sets. Any mathematical entity is a set, whether
or not we choose to think of it that way.
Russell’s Paradox
31
1.10 Russell’s Paradox
This section contains some background information that may be interesting,
but is not used in the remainder of the book.
The philosopher and mathematician Bertrand Russell (1872–1970)
did groundbreaking work on the theory of sets and the foundations of
mathematics. He was probably among the first to understand how the
misuse of sets can lead to bizarre and paradoxical situations. He is famous
for an idea that has come to be known as Russell’s paradox.
Russell’s paradox involves the following set of sets:
A = © X : X is a set and X ∉ X ª.
(1.1)
In words, A is the set of all sets that do not include themselves as elements.
Most sets we can thin
k of are in A. The set Z of integers is not an integer
(i.e., Z ∉ Z) and therefore Z ∈ A. Also ; ∈ A because ; is a set and ; ∉ ;.
Is there a set that is not in A? Consider B = ©©©© . . . ªªªª. Think of B
as a box containing a box, containing a box, containing a box, and so on,
forever. Or a set of Russian dolls, nested one inside the other, endlessly.
The curious thing about B is that it has just one element, namely B itself:
B = © ©©©...ªªª ª.
|
{z
}
B
Thus B ∈ B. As B does not satisfy B ∉ B, Equation (1.1) says B ∉ A.
Russell’s paradox arises from the question “Is A an element of A?”
For a set X , Equation (1.1) says X ∈ A means the same thing as X ∉ X .
So for X = A, the previous line says A ∈ A means the same thing as A ∉ A.
Conclusion: if A ∈ A is true, then it is false; if A ∈ A is false, then it is true.
This is Russell’s paradox.
Initially Russell’s paradox sparked a crisis among mathematicians.
How could a mathematical statement be both true and false? This seemed
to be in opposition to the very essence of mathematics.
The paradox instigated a very careful examination of set theory and
an evaluation of what can and cannot be regarded as a set. Eventually
mathematicians settled upon a collection of axioms for set theory—the
so-called Zermelo-Fraenkel axioms. One of these axioms is the well-
ordering principle of the previous section. Another, the axiom of foundation,
states that no non-empty set X is allowed to have the property X ∩ x 6= ;
for all its elements x. This rules out such circularly defined “sets” as
X = ©X ª introduced above. If we adhere to these axioms, then situations
32
Sets
like Russell’s paradox disappear. Most mathematicians accept all this on
faith and happily ignore the Zermelo-Fraenkel axioms. Paradoxes like
Russell’s do not tend to come up in everyday mathematics—you have to go
out of your way to construct them.
Still, Russell’s paradox reminds us that precision of thought and lan-
guage is an important part of doing mathematics. The next chapter deals
with the topic of logic, a codification of thought and language.
Additional Reading on Sets. For a lively account of Bertrand Russell’s
life and work (including his paradox), see the graphic novel Logicomix: An
Epic Search For Truth, by Apostolos Doxiadis and Christos Papadimitriou.
Also see cartoonist Jessica Hagy’s online strip Indexed—it is based largely
on Venn diagrams.
CHAPTER
2
Logic
ogic is a systematic way of thinking that allows us to deduce new infor-
L mation from old information and to parse the meanings of sentences.
You use logic informally in everyday life and certainly also in doing mathe-
Book of Proof Page 5
