©2,4ª ∈ E. But note that 2 ∉ E, 3 ∉ E and 4 ∉ E.
¤
¤
¤ ª
Consider the set M = © £ 0 0 , £ 1 0 , £ 1 0
0 0
0 1
1 1
of three two-by-two matrices.
£ 0 0 ¤
£ 1 1 ¤
We have 0 0 ∈ M, but 0 1 ∉ M. Letters can serve as symbols denoting a
¤
¤
¤
set’s elements: If a = £ 0 0
0 0 , b = £ 1 0
0 1
and c = £ 1 0
1 1 , then M = ©a, b, cª.
If X is a finite set, its cardinality or size is the number of elements
it has, and this number is denoted as |X |. Thus for the sets above, |A| = 4,
|B| = 2, |C| = 5, |D| = 4, |E| = 3 and |M| = 3.
There is a special set that, although small, plays a big role.
The
empty set
©ª
is the set
that has no elements. We denote it as ;, so ; = ©ª.
©ª
Whenever you see the symbol ;, it stands for
. Observe that |;| = 0. The
empty set is the only set whose cardinality is zero.
©
Be careful in writing the empty set. Don’t write ;ª when you mean ;.
©
These sets can’t be equal because ; contains nothing while ;ª contains
one thing, namely the empty set. If this is confusing, think of a set as a
©
box with things in it, so, for example, 2, 4, 6, 8ª is a “box” containing four
©
numbers. The empty set ; = ©ª is an empty box. By contrast, ;ª is a box
with an empty box inside it. Obviously, there’s a difference: An empty box
is not the same as a box with an empty box inside it. Thus ; 6= ©;ª. (You
¯©
might also note |;| = 0 and ¯ ;ª¯¯ = 1 as additional evidence that ; 6= ©;ª.)
Introduction to Sets
5
This box analogy can help us think about sets. The set F = ©;, ©;ª, ©©;ªªª
may look strange but it is really very simple. Think of it as a box containing
three things: an empty box, a box containing an empty box, and a box
containing a box containing an empty box. Thus |F| = 3. The set G = ©N, Zª
is a box containing two boxes, the box of natural numbers and the box of
integers. Thus |G| = 2.
A special notation called set-builder notation is used to describe sets
that are too big or complex to list between braces. Consider the infinite
set of even integers E = © . . . , −6, −4, −2, 0, 2, 4, 6, . . . ª. In set-builder notation
this set is written as
E = ©2n : n ∈ Zª.
We read the first brace as “the set of all things of form,” and the colon as
“such that.” So the expression E = ©2n : n ∈ Zª is read as “E equals the set of
all things of form 2n , such that n is an element of Z.” The idea is that E
consists of all possible values of 2n, where n takes on all values in Z.
In general, a set X written with set-builder notation has the syntax
X = ©
ª
expression : rule ,
where the elements of X are understood to be all values of “expression”
that are specified by “rule.”
For example, the set E above is the set
of all values the expression 2n that satisfy the rule n ∈ Z. There can
be many ways to express the same set. For example, E = ©2n : n ∈ Zª =
©n : n
ª
is an even integer = ©n : n = 2k, k ∈ Zª.
Another common way of
writing it is
E = ©n ∈ Z : n
ª
is even ,
read “E is the set of all n in Z such that n is even.” Some writers use a bar
ª
instead of a colon; for example, E = ©n ∈ Z | n is even . We use the colon.
Example 1.1
Here are some further illustrations of set-builder notation.
©
ª
1.
n : n is a prime number = ©2,3,5,7,11,13,17,...ª
©
ª
2.
n ∈ N : n is prime = ©2,3,5,7,11,13,17,...ª
©
3.
n2 : n ∈ Zª = ©0,1,4,9,16,25,...ª
p
p
©
4.
x ∈ R : x2 − 2 = 0ª = © 2,− 2ª
©
5.
x ∈ Z : x2 − 2 = 0ª = ;
©
6.
x ∈ Z : |x| < 4ª = © − 3,−2,−1,0,1,2,3ª
©
7.
2x : x ∈ Z,|x| < 4ª = © − 6,−4,−2,0,2,4,6ª
©
8.
x ∈ Z : |2x| < 4ª = © − 1,0,1ª
6
Sets
These last three examples highlight a conflict of notation that we must
always be alert to. The expression |X | means absolute value if X is a number
and cardinality if X is a set. The distinction should always be clear from
©
context. Consider x ∈ Z : |x| < 4ª in Example 1.1 (6) above. Here x ∈ Z, so x
is a number (not a set), and thus the bars in |x| must mean absolute value,
not cardinality. On the other hand, suppose A = ©©1, 2ª, ©3, 4, 5, 6ª, ©7ªª and
B = ©X ∈ A : |X | < 3ª. The elements of A are sets (not numbers), so the |X |
in the expression for B must mean cardinality. Therefore B = ©©1, 2ª, ©7ªª.
We close this section with a summary of special sets. These are sets or
types of sets that come up so often that they are given special names and
symbols.
• The empty set: ; = ©ª
• The natural numbers: N = ©1, 2, 3, 4, 5, . . . ª
• The integers: Z = © . . . , −3, −2, −1, 0, 1, 2, 3, 4, 5, . . . ª
m
• The rational numbers: Q = ©x : x =
, where m, n ∈ Z and n 6= 0ª
n
• The real numbers: R
(the set of all real numbers on the number line)
Notice that Q is the set of all numbers that can be expressed as a fraction
p
p
of two integers. You are surely aware that Q 6= R, as
2 ∉ Q but
2 ∈ R.
Following are some other special sets that you will recall from your
study of calculus. Given two numbers a, b ∈ R with a < b, we can form
various intervals on the number line.
• Closed interval: [a, b] = ©x ∈ R : a ≤ x ≤ bª
• Half open interval: (a, b] = ©x ∈ R : a < x ≤ bª
• Half open interval: [a, b) = ©x ∈ R : a ≤ x < bª
• Open interval: (a, b) = ©x ∈ R : a < x < bª
• Infinite interval: (a, ∞) = ©x ∈ R : a < xª
• Infinite interval: [a, ∞) = ©x ∈ R : a ≤ xª
• Infinite interval: (−∞, b) = ©x ∈ R : x < bª
• Infinite interval: (−∞, b] = ©x ∈ R : x ≤ bª
Remember that these are intervals on the number line, so they have in-
finitely many elements. The set (0.1, 0.2) contains infinitely many numbers,
even though the end points may be close together. It is an unfortunate
notational accident that (a, b) can denote both an interval on the line and
a point on the plane. The difference is usually clear from context. In the
next section we will see still a
nother meaning of (a, b).
Introduction to Sets
7
Exercises for Section 1.1
A. Write each of the following sets by listing their elements between braces.
1. ©5x − 1 : x ∈ Zª
9. ©x ∈ R : sin π x = 0ª
2. ©3x + 2 : x ∈ Zª
10. ©x ∈ R : cos x = 1ª
3. ©x ∈ Z : −2 ≤ x < 7ª
11. ©x ∈ Z : |x| < 5ª
4. ©x ∈ N : −2 < x ≤ 7ª
12. ©x ∈ Z : |2x| < 5ª
5. ©x ∈ R : x2 = 3ª
13. ©x ∈ Z : |6x| < 5ª
6. ©x ∈ R : x2 = 9ª
14. ©5x : x ∈ Z,|2x| ≤ 8ª
7. ©x ∈ R : x2 + 5x = −6ª
15. ©5a + 2b : a, b ∈ Zª
8. ©x ∈ R : x3 + 5x2 = −6xª
16. ©6a + 2b : a, b ∈ Zª
B. Write each of the following sets in set-builder notation.
17. ©2, 4, 8, 16, 32, 64 . . . ª
23. ©3, 4, 5, 6, 7, 8ª
18. ©0, 4, 16, 36, 64, 100, . . . ª
24. © − 4,−3,−2,−1,0,1,2ª
19. © . . . , −6,−3,0,3,6,9,12,15,...ª
25. © . . . , 1 , 1 , 1 , 1, 2, 4, 8, . . . ª
8 4 2
20. © . . . , −8,−3,2,7,12,17,...ª
26. © . . . , 1 , 1 , 1 , 1, 3, 9, 27, . . . ª
27 9 3
21. ©0, 1, 4, 9, 16, 25, 36, . . . ª
27. © . . . , − π,− π ,0, π , π, 3 π ,2 π, 5 π ,...ª
2
2
2
2
22. ©3, 6, 11, 18, 27, 38, . . . ª
28. © . . . , − 3 ,
, 0, 3 , 3 , 9 , 3, 15 , 9 , . . . ª
2 − 3
4
4 2 4
4
2
C. Find the following cardinalities.
29. ¯©©
©
¯
1ª, ©2, ©3, 4ªª, ;ª¯¯
34. ¯¯ x ∈ N : |x| < 10ª¯¯
30. ¯©©
©
¯
1, 4ª, a, b, ©©3, 4ªª, ©;ªª¯¯
35. ¯¯ x ∈ Z : x2 < 10ª¯¯
31. ¯©©©
©
¯
1ª, ©2, ©3, 4ªª, ;ªª¯¯
36. ¯¯ x ∈ N : x2 < 10ª¯¯
32. ¯©©©
©
¯
1, 4ª, a, b, ©©3, 4ªª, ©;ªªª¯¯
37. ¯¯ x ∈ N : x2 < 0ª¯¯
33. ¯©
©
¯
x ∈ Z : |x| < 10ª¯¯
38. ¯¯ x ∈ N : 5x ≤ 20ª¯¯
D. Sketch the following sets of points in the x-y plane.
39. ©(x, y) : x ∈ [1,2], y ∈ [1,2]ª
46. ©(x, y) : x, y ∈ R, x2 + y2 ≤ 1ª
40. ©(x, y) : x ∈ [0,1], y ∈ [1,2]ª
47. ©(x, y) : x, y ∈ R, y ≥ x2 − 1ª
41. ©(x, y) : x ∈ [−1,1], y = 1ª
48. ©(x, y) : x, y ∈ R, x > 1ª
42. ©(x, y) : x = 2, y ∈ [0,1]ª
49. ©(x, x + y) : x ∈ R, y ∈ Zª
43. ©(x, y) : |x| = 2, y ∈ [0,1]ª
50. ©(x, x2 ) : x
y
∈ R, y ∈ Nª
44. ©(x, x2) : x ∈ Rª
51. ©(x, y) ∈ R2 : (y − x)(y + x) = 0ª
45. ©(x, y) : x, y ∈ R, x2 + y2 = 1ª
52. ©(x, y) ∈ R2 : (y − x2)(y + x2) = 0ª
8
Sets
1.2 The Cartesian Product
Given two sets A and B, it is possible to “multiply” them to produce a new
set denoted as A × B. This operation is called the Cartesian product. To
understand it, we must first understand the idea of an ordered pair.
Definition 1.1
An ordered pair is a list (x, y) of two things x and y,
enclosed in parentheses and separated by a comma.
For example, (2, 4) is an ordered pair, as is (4, 2). These ordered pairs
are different because even though they have the same things in them,
the order is different. We write (2, 4) 6= (4, 2). Right away you can see that
ordered pairs can be used to describe points on the plane, as was done in
calculus, but they are not limited to just that. The things in an ordered
pair don’t have to be numbers. You can have ordered pairs of letters, such
as (m, `), ordered pairs of sets such as (©2, 5ª, ©3, 2ª), even ordered pairs
of ordered pairs like ((2, 4), (4, 2)). The following are also ordered pairs:
(2, ©1, 2, 3ª), (R,(0,0)). Any list of two things enclosed by parentheses is an
ordered pair. Now we are ready to define the Cartesian product.
Definition 1.2
The Cartesian product of two sets A and B is another
set, denoted as A × B and defined as A × B = ©(a, b) : a ∈ A, b ∈ Bª.
Thus A × B is a set of ordered pairs of elements from A and B. For
example, if A = ©k, `, mª and B = ©q, rª, then
A × B = ©(k, q),(k, r),( `, q),( `, r),(m, q),(m, r)ª.
Figure 1.1 shows how to make a schematic diagram of A × B. Line up the
elements of A horizontally and line up the elements of B vertically, as if A
and B form an x- and y-axis. Then fill in the ordered pairs so that each
element (x, y) is in the column headed by x and the row headed by y.
B
A × B
r
(k, r)
( `, r) (m, r)
q
(k, q)
( `, q) (m, q)
A
k
`
m
Figure 1.1. A diagram of a Cartesian product
The Cartesian Product
9
©
For another example, 0, 1ª × ©2, 1ª = ©(0, 2), (0, 1), (1, 2), (1, 1)ª. If you are
a visual thinker, you may wish to draw a diagram similar to Figure 1.1.
The rectangular array of such diagrams give us the following general fact.
Fact 1.1
If A and B are finite sets, then |A × B| = |A| · |B|.
The set R × R = ©(x, y) : x, y ∈ Rª should be very familiar. It can be viewed
as the set of points on the Cartesian plane, and is drawn in Figure 1.2(a).
The set R × N = ©(x, y) : x ∈ R, y ∈ Nª can be regarded as all of the points on
the Cartesian plane whose second coordinate is a natural number. This
is illustrated in Figure 1.2(b), which shows that R × N looks like infinitely
many horizontal lines at integer heights above the x axis. The set N × N
can be visualized as the set of all points on the Cartesian plane whose
coordinates are both natural numbers. It looks like a grid of dots in the
first quadrant, as illustrated in Figure 1.2(c).
y
y
y
x
x
x
R × R
R × N
N × N
(a)
(b)
(c)
Figure 1.2. Drawings of some Cartesian products
It is even possible for one factor of a Cartesian product to be a Cartesian
product itself, as in R × (N × Z) = ©(x, ( y, z)) : x ∈ R, ( y, z) ∈ N × Zª.
We can also define Cartesian products of three or more sets by moving
beyond ordered pairs. An ordered triple is a list (x, y, z). The Cartesian
product of the three sets R, N and Z is R × N × Z = ©(x, y, z) : x ∈ R, y ∈ N, z ∈ Zª.
Of course there is no reason to stop with ordered triples. In general,
A1 × A2 × ··· × An = ©(x1, x2,..., xn) : xi ∈ Ai for each i = 1,2,..., nª.
Be mindf
ul of parentheses. There is a slight difference between R×(N×Z)
and R × N × Z. The first is a Cartesian product of two sets; its elements are
ordered pairs (x, ( y, z)). The second is a Cartesian product of three sets; its
elements look like (x, y, z). To be sure, in many situations there is no harm
in blurring the distinction between expressions like (x, ( y, z)) and (x, y, z),
but for now we consider them as different.
10
Sets
We can also take Cartesian powers of sets. For any set A and positive
integer n, the power An is the Cartesian product of A with itself n times:
An = A × A × ··· × A = ©(x1, x2,..., xn) : x1, x2,..., xn ∈ Aª.
In this way, R2 is the familiar Cartesian plane and R3 is three-dimensional
space. You can visualize how, if R2 is the plane, then Z2 = ©(m, n) : m, n ∈ Zª
is a grid of points on the plane. Likewise, as R3 is 3-dimensional space,
Z3 = ©(m, n, p) : m, n, p ∈ Zª is a grid of points in space.
In other courses you may encounter sets that are very similar to Rn,
but yet have slightly different shades of meaning. Consider, for example,
the set of all two-by-three matrices with entries from R:
M = ©£ u v w ¤
x y z
: u, v, w, x, y, z ∈ Rª.
This is not really all that different from the set
R6 = ©(u,v,w, x, y, z) : u,v,w, x, y, z ∈ Rª.
The elements of these sets are merely certain arrangements of six real
numbers. Despite their similarity, we maintain that M 6= R6, for two-by-
three matrices are not the same things as sequences of six numbers.
Exercises for Section 1.2
A. Write out the indicated sets by listing their elements between braces.
1. Suppose A = ©1,2,3,4ª and B = ©a, cª.
(a) A × B
(c) A × A
(e) ; × B
(g) A × (B × B)
(b) B × A
(d) B × B
(f) (A × B) × B
(h) B3
2. Suppose A = © π, e,0ª and B = ©0,1ª.
(a) A × B
(c) A × A
(e) A × ;
(g) A × (B × B)
(b) B × A
(d) B × B
(f) (A × B) × B
(h) A × B × B
3. ©x ∈ R : x2 = 2ª × ©a, c, eª
6. ©x ∈ R : x2 = xª × ©x ∈ N : x2 = xª
4. ©n ∈ Z : 2 < n < 5ª × ©n ∈ Z : |n| = 5ª
7. ©;ª × ©0,;ª × ©0,1ª
5. ©x ∈ R : x2 = 2ª × ©x ∈ R : |x| = 2ª
8. ©0, 1ª4
B. Sketch these Cartesian products on the x-y plane R2 (or R3 for the last two).
9. ©1, 2, 3ª × © − 1,0,1ª
15. ©1ª × [0,1]
10. © − 1,0,1ª × ©1,2,3ª
16. [0, 1] × ©1ª
11. [0, 1] × [0,1]
17. N × Z
12. [−1,1] × [1,2]
Book of Proof Page 2
