The difference A − B is the set of all things that are in A but not in B.
Example 1.5
Suppose A = ©a, b, c, d, eª, B = ©d, e, f ª and C = ©1, 2, 3ª.
1. A ∪ B = ©a, b, c, d, e, f ª
2. A ∩ B = ©d, eª
3. A − B = ©a, b, cª
4. B − A = © f ª
5. (A − B) ∪ (B − A) = ©a, b, c, f ª
6. A ∪ C = ©a, b, c, d, e, 1, 2, 3ª
7. A ∩ C = ;
8. A − C = ©a, b, c, d, eª
9. (A ∩ C) ∪ (A − C) = ©a, b, c, d, eª
10. (A ∩ B) × B = ©(d, d), (d, e), (d, f ), (e, d), (e, e), (e, f )ª
11. (A × C) ∩ (B × C) = ©(d, 1), (d, 2), (d, 3), (e, 1), (e, 2), (e, 3)ª
Observe that for any sets X and Y it is always true that X ∪ Y = Y ∪ X
and X ∩ Y = Y ∩ X , but in general X − Y 6= Y − X .
Continuing the example, parts 12–15 below use the interval notation
discussed in Section 1.1, so [2, 5] = ©x ∈ R : 2 ≤ x ≤ 5ª, etc. Sketching these
examples on the number line may help you understand them.
12. [2, 5] ∪ [3, 6] = [2, 6]
13. [2, 5] ∩ [3, 6] = [3, 5]
14. [2, 5] − [3, 6] = [2, 3)
15. [0, 3] − [1, 2] = [0, 1) ∪ (2, 3]
18
Sets
A ∪ B
A − B
B
A ∩ B
A
(a)
(b)
(c)
(d)
Figure 1.5. The union, intersection and difference of sets A and B
Example 1.6
Let A = ©(x, x2) : x ∈ Rª be the graph of the equation y = x2
and let B = ©(x, x+2) : x ∈ Rª be the graph of the equation y = x+2. These sets
are subsets of R2. They are sketched together in Figure 1.5(a). Figure 1.5(b)
shows A ∪ B, the set of all points (x, y) that are on one (or both) of the two
graphs. Observe that A ∩ B = ©(−1, 1), (2, 4)ª consists of just two elements,
the two points where the graphs intersect, as illustrated in Figure 1.5(c).
Figure 1.5(d) shows A−B, which is the set A with “holes” where B crossed it.
In set builder notation, we could write A ∪B = ©(x, y) : x ∈ R, y = x2 or y = x+2ª
and A − B = ©(x, x2) : x ∈ R − © − 1, 2ªª.
Exercises for Section 1.5
1. Suppose A = ©4,3,6,7,1,9ª, B = ©5,6,8,4ª and C = ©5,8,4ª. Find:
(a) A ∪ B
(d) A − C
(g) B ∩ C
(b) A ∩ B
(e) B − A
(h) B ∪ C
(c) A − B
(f) A ∩ C
(i) C − B
2. Suppose A = ©0,2,4,6,8ª, B = ©1,3,5,7ª and C = ©2,8,4ª. Find:
(a) A ∪ B
(d) A − C
(g) B ∩ C
(b) A ∩ B
(e) B − A
(h) C − A
(c) A − B
(f) A ∩ C
(i) C − B
3. Suppose A = ©0,1ª and B = ©1,2ª. Find:
(a) (A × B) ∩ (B × B)
(d) (A ∩ B) × A
(g) P(A) − P(B)
(b) (A × B) ∪ (B × B)
(e) (A × B) ∩ B
(h) P(A ∩ B)
(c) (A × B) − (B × B)
(f) P(A) ∩ P(B)
(i) P(A × B)
4. Suppose A = ©b, c, dª and B = ©a, bª. Find:
(a) (A × B) ∩ (B × B)
(d) (A ∩ B) × A
(g) P(A) − P(B)
(b) (A × B) ∪ (B × B)
(e) (A × B) ∩ B
(h) P(A ∩ B)
(c) (A × B) − (B × B)
(f) P(A) ∩ P(B)
(i) P(A) × P(B)
Complement
19
5. Sketch the sets X = [1,3]×[1,3] and Y = [2,4]×[2,4] on the plane R2. On separate
drawings, shade in the sets X ∪ Y , X ∩ Y , X − Y and Y − X . (Hint: X and Y are
Cartesian products of intervals. You may wish to review how you drew sets
like [1, 3] × [1, 3] in the exercises for Section 1.2.)
6. Sketch the sets X = [−1,3] × [0,2] and Y = [0,3] × [1,4] on the plane R2. On
separate drawings, shade in the sets X ∪ Y , X ∩ Y , X − Y and Y − X .
7. Sketch the sets X = ©(x, y) ∈ R2 : x2 + y2 ≤ 1ª and Y = ©(x, y) ∈ R2 : x ≥ 0ª on R2. On
separate drawings, shade in the sets X ∪ Y , X ∩ Y , X − Y and Y − X .
8. Sketch the sets X = ©(x, y) ∈ R2 : x2 + y2 ≤ 1ª and Y = ©(x, y) ∈ R2 : −1 ≤ y ≤ 0ª on R2.
On separate drawings, shade in the sets X ∪ Y , X ∩ Y , X − Y and Y − X .
9. Is the statement (R×Z)∩(Z×R) = Z×Z true or false? What about the statement
(R × Z) ∪ (Z × R) = R × R?
10. Do you think the statement (R − Z) × N = (R × N) − (Z × N) is true, or false? Justify.
1.6 Complement
This section introduces yet another set operation, called the set complement.
The definition requires the idea of a universal set, which we now discuss.
When dealing with a set, we almost always regard it as a subset
of some larger set.
For example, consider the set of prime numbers
P = ©2,3,5,7,11,13,...ª. If asked to name some things that are not in P, we
might mention some composite numbers like 4 or 6 or 423. It probably
would not occur to us to say that Vladimir Putin is not in P. True, Vladimir
Putin is not in P, but he lies entirely outside of the discussion of what is
a prime number and what is not. We have an unstated assumption that
P ⊆ N
because N is the most natural setting in which to discuss prime numbers.
In this context, anything not in P should still be in N. This larger set N is
called the universal set or universe for P.
Almost every useful set in mathematics can be regarded as having
some natural universal set. For instance, the unit circle is the set C =
©(x, y) ∈ R2 : x2 + y2 = 1ª, and since all these points are in the plane R2 it is
natural to regard R2 as the universal set for C. In the absence of specifics,
if A is a set, then its universal set is often denoted as U. We are now
ready to define the complement operation.
Definition 1.6
Let A be a set with a universal set U. The complement
of A, denoted A, is the set A = U − A.
20
Sets
Example 1.7
If P is the set of prime numbers, then
P = N − P = ©1,4,6,8,9,10,12,...ª.
Thus P is the set of composite numbers and 1.
Example 1.8
Let A = ©(x, x2) : x ∈ Rª be the graph of the equation y = x2.
Figure 1.6(a) shows A in its universal set R2. The complement of A is A =
R2 − A = ©(x, y) ∈ R2 : y 6= x2ª, illustrated by the shaded area in Figure 1.6(b).
A
A
(a)
(b)
Figure 1.6. A set and its complement
Exercises for Section 1.6
1. Let A = ©4,3,6,7,1,9ª and B = ©5,6,8,4ª have universal set U = ©0,1,2,...,10ª.
Find:
(a) A
(d) A ∪ A
(g) A − B
(b) B
(e) A − A
(h) A ∩ B
(c) A ∩ A
(f) A − B
(i) A ∩ B
2. Let A = ©0,2,4,6,8ª and B = ©1,3,5,7ª have universal set U = ©0,1,2,...,8ª. Find:
(a) A
(d) A ∪ A
(g) A ∩ B
(b) B
(e) A − A
/> (h) A ∩ B
(c) A ∩ A
(f) A ∪ B
(i) A × B
3. Sketch the set X = [1,3]×[1,2] on the plane R2. On separate drawings, shade in
the sets X and X ∩ ([0, 2] × [0, 3]).
4. Sketch the set X = [−1,3] × [0,2] on the plane R2. On separate drawings, shade
in the sets X and X ∩ ([−2, 4] × [−1, 3]).
5. Sketch the set X = ©(x, y) ∈ R2 : 1 ≤ x2 + y2 ≤ 4ª on the plane R2. On a separate
drawing, shade in the set X .
6. Sketch the set X = ©(x, y) ∈ R2 : y < x2ª on R2. Shade in the set X .
Venn Diagrams
21
1.7 Venn Diagrams
In thinking about sets, it is sometimes helpful to draw informal, schematic
diagrams of them. In doing this we often represent a set with a circle
(or oval), which we regard as enclosing all the elements of the set. Such
diagrams can illustrate how sets combine using various operations. For
example, Figures 1.7(a–c) show two sets A and B that overlap in a middle
region.
The sets A ∪ B, A ∩ B and A − B are shaded.
Such graphical
representations of sets are called Venn diagrams, after their inventor,
British logician John Venn, 1834–1923.
A ∪ B
A ∩ B
A − B
A
B
A
B
A
B
(a)
(b)
(c)
Figure 1.7. Venn diagrams for two sets
Though you are unlikely to draw Venn diagrams as a part of a proof
of any theorem, you will probably find them to be useful “scratch work”
devices that help you to understand how sets combine, and to develop
strategies for proving certain theorems or solving certain problems. The
remainder of this section uses Venn diagrams to explore how three sets
can be combined using ∪ and ∩.
Let’s begin with the set A ∪ B ∪ C. Our definitions suggest this should
consist of all elements which are in one or more of the sets A, B and C.
Figure 1.8(a) shows a Venn diagram for this. Similarly, we think of A∩B∩C
as all elements common to each of A, B and C, so in Figure 1.8(b) the
region belonging to all three sets is shaded.
C
C
A
B
A
B
A ∪ B ∪ C
A ∩ B ∩ C
(a)
(b)
Figure 1.8. Venn diagrams for three sets
22
Sets
We can also think of A ∩ B ∩ C as the two-step operation (A ∩ B) ∩ C. In
this expression the set A ∩ B is represented by the region common to both
A and B, and when we intersect this with C we get Figure 1.8(b). This is a
visual representation of the fact that A ∩ B ∩ C = (A ∩ B) ∩ C. Similarly, we
have A ∩ B ∩ C = A ∩ (B ∩ C). Likewise, A ∪ B ∪ C = (A ∪ B) ∪ C = A ∪ (B ∪ C).
Notice that in these examples, where the expression either contains
only the symbol ∪ or only the symbol ∩, the placement of the parentheses
is irrelevant, so we are free to drop them. It is analogous to the situations
in algebra involving expressions (a + b) + c = a + (b + c) or (a · b) · c = a · (b · c).
We tend to drop the parentheses and write simply a + b + c or a · b · c. By
contrast, in an expression like (a + b) · c the parentheses are absolutely
essential because (a + b) · c and a + (b · c) are generally not equal.
Now let’s use Venn diagrams to help us understand the expressions
(A ∪ B) ∩ C and A ∪ (B ∩ C), which use a mix of ∪ and ∩. Figure 1.9 shows
how to draw a Venn diagram for (A ∪ B) ∩ C. In the drawing on the left, the
set A ∪ B is shaded with horizontal lines, while C is shaded with vertical
lines. Thus the set (A ∪ B) ∩ C is represented by the cross-hatched region
where A ∪ B and C overlap. The superfluous shadings are omitted in the
drawing on the right showing the set (A ∪ B) ∩ C.
C
C
A
B
A
B
Figure 1.9. How to make a Venn diagram for (A ∪ B) ∩ C
Now think about A ∪ (B ∩ C). In Figure 1.10 the set A is shaded with
horizontal lines, and B∩C is shaded with vertical lines. The union A∪(B∩C)
is represented by the totality of all shaded regions, as shown on the right.
C
C
A
B
A
B
Figure 1.10. How to make a Venn diagram for A ∪ (B ∩ C)
Venn Diagrams
23
Compare the diagrams for (A ∪ B) ∩ C and A ∪ (B ∩ C) in Figures 1.9 and
1.10. The fact that the diagrams are different indicates that (A ∪ B) ∩ C 6=
A ∪ (B ∩ C) in general. Thus an expression such as A ∪ B ∩ C is absolutely
meaningless because we can’t tell whether it means (A ∪B)∩C or A ∪(B∩C).
In summary, Venn diagrams have helped us understand the following.
Important Points:
• If an expression involving sets uses only ∪, then parentheses are optional.
• If an expression involving sets uses only ∩, then parentheses are optional.
• If an expression uses both ∪ and ∩, then parentheses are essential.
In the next section we will study types of expressions that use only ∪
or only ∩. These expressions will not require the use of parentheses.
Exercises for Section 1.7
1. Draw a Venn diagram for A.
2. Draw a Venn diagram for B − A.
3. Draw a Venn diagram for (A − B) ∩ C.
4. Draw a Venn diagram for (A ∪ B) − C.
5. Draw Venn diagrams for A∪(B∩C) and (A∪B)∩(A∪C). Based on your drawings,
do you think A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)?
6. Draw Venn diagrams for A∩(B∪C) and (A∩B)∪(A∩C). Based on your drawings,
do you think A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)?
7. Suppose sets A and B are in a universal set U. Draw Venn diagrams for A ∩ B
and A ∪ B. Based on your drawings, do you think it’s true that A ∩ B = A ∪ B?
8. Suppose sets A and B are in a universal set U. Draw Venn diagrams for A ∪ B
and A ∩ B. Based on your drawings, do you think it’s true that A ∪ B = A ∩ B?
9. Draw a Venn diagram for (A ∩ B) − C.
10. Draw a Venn diagram for (A − B) ∪ C.
Following are Venn diagrams for expressions involving sets A, B and C. Write the
corresponding expression.
C
C
C
C
11.
A
B
12.
A
B
13.
A
B
14.
A
B
24
Sets
1.8 Indexed Sets
When a mathematical problem involves lots of sets, it is often convenient to
keep track of them by using subscripts (also called indices). Thus instead
of denoting three sets as A, B and C, we might instead write them as A1, A2
and A3. These are called indexed sets.
Although we defined union and intersection to be operations that
combine two sets, you by now have no difficulty formi
ng unions and
intersections of three or more sets. (For instance, in the previous section
we drew Venn diagrams for the intersection and union of three sets.)
But let’s take a moment to write down careful definitions. Given sets
A1, A2, . . . , An, the set A1 ∪ A2 ∪ A3 ∪ ··· ∪ An consists of everything that is
in at least one of the sets Ai. Likewise A1 ∩ A2 ∩ A3 ∩ · · · ∩ An consists of
everything that is common to all of the sets Ai. Here is a careful definition.
Definition 1.7
Suppose A1, A2, . . . , An are sets. Then
A1 ∪ A2 ∪ A3 ∪ ··· ∪ An = ©x : x ∈ Ai for at least one set Ai, for 1 ≤ i ≤ nª,
A1 ∩ A2 ∩ A3 ∩ ··· ∩ An = ©x : x ∈ Ai for every set Ai, for 1 ≤ i ≤ nª.
But if the number n of sets is large, these expressions can get messy.
To overcome this, we now develop some notation that is akin to sigma
notation. You already know that sigma notation is a convenient symbolism
for expressing sums of many numbers. Given numbers a1, a2, a3, . . . , an,
then
n
X ai = a1 + a2 + a3 + ··· + an.
i=1
Even if the list of numbers is infinite, the sum
∞
X ai = a1 + a2 + a3 + ··· + ai + ···
i=1
is often still meaningful. The notation we are about to introduce is very
similar to this. Given sets A1, A2, A3, . . . , An, we define
n
n
[ A
i = A1 ∪ A2 ∪ A3 ∪ · · · ∪ An
and
Ai = A1 ∩ A2 ∩ A3 ∩ ··· ∩ An.
i=1
i=1
Example 1.9
Suppose A1 = ©0, 2, 5ª, A2 = ©1, 2, 5ª and A3 = ©2, 5, 7ª. Then
3
3
[ A
i = A1 ∪ A2 ∪ A3 = ©0, 1, 2, 5, 7ª
and
Ai = A1 ∩ A2 ∩ A3 = ©2,5ª.
i=1
i=1
Indexed Sets
25
This notation is also used when the list of sets A1, A2, A3, . . . is infinite:
∞
[ Ai = A1 ∪ A2 ∪ A3 ∪ ··· = ©x : x ∈ Ai for at least one set Ai with 1 ≤ iª.
i=1
∞
Ai = A1 ∩ A2 ∩ A3 ∩ ··· = ©x : x ∈ Ai for every set Ai with 1 ≤ iª.
i=1
Example 1.10
This example involves the following infinite list of sets.
A1 = © − 1,0,1ª, A2 = © − 2,0,2ª, A3 = © − 3,0,3ª, ··· , Ai = © − i,0, iª, ···
∞
∞
[
Observe that
Ai = Z, and
Ai = ©0ª.
i=1
i=1
Here is a useful twist on our new notation. We can write
3
[ Ai = [ Ai,
i=1
Book of Proof Page 4