Book of Proof
Page 3
18. Z × Z
13. ©1, 1.5, 2ª × [1,2]
19. [0, 1] × [0,1] × [0,1]
14. [1, 2] × ©1,1.5,2ª
20. ©(x, y) ∈ R2 : x2 + y2 ≤ 1ª × [0,1]
Subsets
11
1.3 Subsets
It can happen that every element of some set A is also an element of
another set B. For example, each element of A = ©0, 2, 4ª is also an element
of B = ©0, 1, 2, 3, 4ª. When A and B are related this way we say that A is a
subset of B.
Definition 1.3
Suppose A and B are sets. If every element of A is also
an element of B, then we say A is a subset of B, and we denote this as
A ⊆ B. We write A 6⊆ B if A is not a subset of B, that is, if it is not true
that every element of A is also an element of B. Thus A 6⊆ B means that
there is at least one element of A that is not an element of B.
Example 1.2
Be sure you understand why each of the following is true.
©
1.
2, 3, 7ª ⊆ ©2,3,4,5,6,7ª
©
2.
2, 3, 7ª 6⊆ ©2,4,5,6,7ª
©
3.
2, 3, 7ª ⊆ ©2,3,7ª
©
4.
2n : n ∈ Zª ⊆ Z
©
5.
(x, sin(x)) : x ∈ Rª ⊆ R2
©
6.
2, 3, 5, 7, 11, 13, 17, . . . ª ⊆ N
7. N ⊆ Z ⊆ Q ⊆ R
8. R × N ⊆ R × R
This brings us to a significant fact: If B is any set whatsoever, then
; ⊆ B. To see why this is true, look at the last sentence of Definition 1.3.
It says that ; 6⊆ B would mean that there is at least one element of ;
that is not an element of B. But this cannot be so because ; contains no
elements! Thus it is not the case that ; 6⊆ B, so it must be that ; ⊆ B.
Fact 1.2
The empty set is a subset of every set, that is, ; ⊆ B for any set B.
Here is another way to look at it. Imagine a subset of B as a thing you
©ª
make by starting with braces
, then filling them with selections from B.
©ª
For example, to make one particular subset of B = ©a, b, cª, start with
,
©ª
©
select b and c from B and insert them into
to form the subset
b, cª.
©
Alternatively, you could have chosen just a to make aª, and so on. But
one option is to simply select nothing from B. This leaves you with the
©ª
©ª
subset
. Thus
⊆ B. More often we write it as ; ⊆ B.
12
Sets
This idea of “making” a subset can help us list out all the subsets of
a given set B. As an example, let B = ©a, b, cª. Let’s list all of its subsets.
One way of approaching this is to make a tree-like structure. Begin with
©ª
the subset
, which is shown on the left of Figure 1.3. Considering the
©ª
element a of B, we have a choice: insert it or not. The lines from
point
©ª
©
to what we get depending whether or not we insert a, either
or aª. Now
move on to the element b of B. For each of the sets just formed we can
either insert or not insert b, and the lines on the diagram point to the
©ª
©
©
©
resulting sets
, bª, aª, or a, bª. Finally, to each of these sets, we can
either insert c or not insert it, and this gives us, on the far right-hand
©ª
©
©
©
©
©
©
©
column, the sets
, cª, bª, b, cª, aª, a, cª, a, bª and a, b, cª. These are
the eight subsets of B = ©a, b, cª.
Insert a ?
Insert b ?
Insert c ?
©ª
©ª
No
Yes
©
No
cª
©ª
©
Yes
bª
©
No
No
bª
Yes
©b, cª
©ª
©aª
©
No
Yes
aª
Yes
©
No
a, cª
©aª
©
Yes
a, bª
©
No
a, bª
Yes
©a, b, cª
Figure 1.3. A “tree” for listing subsets
We can see from the way this tree branches out that if it happened that
B = ©aª, then B would have just two subsets, those in the second column
of the diagram. If it happened that B = ©a, bª, then B would have four
subsets, those listed in the third column, and so on. At each branching of
the tree, the number of subsets doubles. Thus in general, if |B| = n, then
B must have 2n subsets.
Fact 1.3
If a finite set has n elements, then it has 2n subsets.
Subsets
13
For a slightly more complex example, consider listing the subsets of
B = ©1,2,©1,3ªª
©
. This B has just three elements: 1, 2 and 1, 3ª. At this
point you probably don’t even have to draw a tree to list out B’s subsets.
You just make all the possible selections from B and put them between
braces to get
©ª, ©1ª, ©2ª, ©©1,3ªª, ©1,2ª, ©1,©1,3ªª, ©2,©1,3ªª, ©1,2,©1,3ªª.
These are the eight subsets of B. Exercises like this help you identify what
©
is and isn’t a subset. You know immediately that a set such as 1, 3ª is not
a subset of B because it can’t be made by selecting elements from B, as
the 3 is not an element of B and thus is not a valid selection. Notice that
©
©
©©
although 1, 3ª 6⊆ B, it is true that 1, 3ª ∈ B. Also,
1, 3ªª ⊆ B.
Example 1.3
Be sure you understand why the following statements are
true. Each illustrates an aspect of set theory that you’ve learned so far.
©
1. 1 ∈ ©1, ©1ªª . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 is the first element listed in 1, ©1ªª
2. 1 6⊆ ©1, ©1ªª . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . because 1 is not a set
©
©
©
3.
1ª ∈ ©1,©1ªª . . . . . . . . . . . . . . . . . . . . . . . . . 1ª is the second element listed in 1,©1ªª
©
©
©
4.
1ª ⊆ ©1,©1ªª . . . . . . . . . . . . . . . . . . . . . . . make subset 1ª by selecting 1 from 1,©1ªª
©©
©
©
©©
5.
1ªª ∉ ©1,©1ªª . . . . . . . . . . . because 1,©1ªª contains only 1 and 1ª, and not
1ªª
©©
©©
©
©
6.
1ªª ⊆ ©1,©1ªª. . . . . . . . . . . . . . . . . .make subset
1ªª by selecting 1ª from 1,©1ªª
7. N ∉ N . . . . . . . . . because N is a set (not a number) and N contains only numbers
8. N ⊆ N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . because X ⊆ X for every set X
9. ; ∉ N . . . . . . . . . . . . . . . . . . . . because the set N contains only numbers and no sets
10. ; ⊆ N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . because ; is a subset of every set
©
11. N ∈ ©Nª . . . . . . . . . . . . . . . . . . . . . . . . . . . because Nª has just one element, the set N
12. N 6⊆ ©Nª . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . because, for instance, 1 ∈ N but 1 ∉ ©Nª
©
13. ; ∉ ©Nª . . . . . . . . . . . . . . . . . . . . . note that the only element of Nª is N, and N 6= ;
14. ; ⊆ ©Nª . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . because ; is a subset of every set
©
15. ; ∈ ©;, Nª . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ; is the first element listed in ;, Nª
16. ; ⊆ ©;, Nª . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . because ; is a subset of every set
©
©
©
17.
Nª ⊆ ©;,Nª . . . . . . . . . . . . . . . . . . . . . . . make subset Nª by selecting N from ;,Nª
©
18.
Nª 6⊆ ©;,©Nªª . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . because N ∉ ©;,©Nªª
©
©
©
19.
Nª ∈ ©;,©Nªª. . . . . . . . . . . . . . . . . . . . . . Nª is the second element listed in ;,©Nªª
©
20.
(1, 2), (2, 2), (7, 1)ª ⊆ N × N . . . . . . . . . . . . . . . . . . . each of (1,2), (2,2), (7,1) is in N × N
Though they should help you understand the concept of subset, the
above examples are somewhat artificial. But in general, subsets arise very
14
Sets
naturally. For instance, consider the unit circle C = ©(x, y) ∈ R2 : x2 + y2 = 1ª.
This is a subset C ⊆ R2. Likewise the graph of a function y = f (x) is a set
of points G = ©(x, f (x)) : x ∈ Rª, and G ⊆ R2. Surely sets such as C and G
are more easily understood or visualized when regarded as subsets of R2.
Mathematics is filled with such instances where it is important to regard
one set as a subset of another.
Exercises for Section 1.3
A. List all the subsets of the following sets.
1. ©1, 2, 3, 4ª
5. ©;ª
2. ©1, 2, ;ª
6. ©R,Q,Nª
3. ©©Rªª
7. ©R,©Q,Nªª
4. ;
8. © ©0, 1ª, ©0, 1, ©2ªª, ©0ª ª
B. Write out the following sets by listing their elements between braces.
9. ©X : X ⊆ ©3,2, aª and |X | = 2ª
11. ©X : X ⊆ ©3,2, aª and |X | = 4ª
10. ©X ⊆ N : |X | ≤ 1ª
12. ©X : X ⊆ ©3,2, aª and |X | = 1ª
C. Decide if the following statements are true or false. Explain.
13. R3 ⊆ R3
15. ©(x, y) : x − 1 = 0ª ⊆ ©(x, y) : x2 − x = 0ª
14. R2 ⊆ R3
16. ©(x, y) : x2 − x = 0ª ⊆ ©(x, y) : x − 1 = 0ª
1.4 Power Sets
Given a set, you can form a new set with the power set operation, defined
as follows.
Definition 1.4
If A is a set, the power set of A is another set, denoted
as P(A) and defined to be the set of all subsets of A. In symbols, P(A) =
© X : X ⊆ Aª.
For example, suppose A = ©1, 2, 3ª. The power set of A is the set of all
subsets of A. We learned how to find these subsets in the previous section,
©ª
©
©
©
©
©
©
©
and they are
, 1ª, 2ª, 3ª, 1, 2ª, 1, 3ª, 2, 3ª and 1, 2, 3ª. Therefore the
power set of A is
P(A) = © ;, ©1ª, ©2ª, ©3ª, ©1,2ª, ©1,3ª, ©2,3ª, ©1,2,3ª ª.
As we saw in the previous section, if a finite set A has n elements, then
it has 2n subsets, and thus its power set has 2n elements.
Power Sets
15
Fact 1.4
If A is a finite set, then |P(A)| = 2|A|.
Example 1.4
You should examine the following statements and make
sure you understand how the answers were obtained. In particular, notice
that in each instance the equation |P(A)| = 2|A| is true.
1. P ¡©0, 1, 3ª¢ = © ;, ©0ª, ©1ª, ©3ª, ©0, 1ª, ©0, 3ª, ©1, 3ª, ©0, 1, 3ª ª
2. P ¡©1, 2ª¢ = © ;, ©1ª, ©2ª, ©1, 2ª ª
3. P ¡©1ª¢ = © ;, ©1ª ª
4. P (;) = © ; ª
5. P ¡©aª¢ = © ;, ©aª ª
6. P ¡©;ª¢ = © ;, ©;ª ª
7. P ¡©aª¢ × P ¡©;ª¢ = © (;, ;), ¡;, ©;ª¢ , ¡©aª, ;¢ , ¡©aª, ©;ª¢ ª
8. P ¡P ¡©;ª¢¢ = © ;, ©;ª, ©©;ªª, ©;, ©;ªª ª
9. P ¡©1, ©1, 2ªª¢ = © ;, ©1ª, ©©1, 2ªª, ©1, ©1, 2ªª ª
10. P ¡©Z, Nª¢ = © ;, ©Zª, ©Nª, ©Z, Nª ª
Next are some that are wrong. See if you can determine why they are wrong
and make sure you understand the explanation on the right.
11. P(1) = © ;, ©1ª ª . . . . . . . . . . . . . . . . . . . . . . . . . . . meaningless because 1 is not a set
©
12. P ¡©1, ©1, 2ªª¢ = ©;, ©1ª, ©1, 2ª, ©1, ©1, 2ªªª . . . . . . . . wrong because 1, 2ª 6⊆ ©1, ©1, 2ªª
©©
13. P ¡©1, ©1, 2ªª¢ = ©;, ©©1ªª, ©©1, 2ªª, ©;, ©1, 2ªªª . . . . . wrong because
1ªª 6⊆ ©1,©1,2ªª
If A is finite, it is possible (though maybe not practical) to list out P(A)
between braces as was done in the above example. That is not possible if
A is infinite. For example, consider P(N). If you start listing its elements
you quickly discover that N has infinitely many subsets, and it’s not clear
how (or if) they could be arranged as a list with a definite pattern:
P(N) = ©;,©1ª,©2ª,...,©1,2ª,©1,3ª,...,©39,47ª,
. . . , ©3, 87, 131ª, . . . , ©2, 4, 6, 8, . . . ª, . . . ? . . . ª.
The set P(R2) is mind boggling. Think of R2 = ©(x, y) : x, y ∈ Rª as the set
of all points on the Cartesian plane. A subset of R2 (that is, an element
of P(R2)) is a set of points in the plane. Let’s look at some of these sets.
©
©
Since (0, 0), (1, 1)ª ⊆ R2, we know that (0, 0), (1, 1)ª ∈ P(R2). We can even
draw a picture of this subset, as in Figure 1.4(a). For another example, the
graph of the equation y = x2 is the set of points G = ©(x, x2) : x ∈ Rª and this
is a subset of R2, so G ∈ P(R2). Figure 1.4(b) is a picture of G. Because
this can be done for any function, the graph of any imaginable function
f : R → R is an element of P(R2).
16
Sets
y
y
y
x
x
x
(a)
(b)
(c)
Figure 1.4. Three of the many, many sets in P(R2)
In fact, any black-and-white image on the plane can be thought of as a
subset of R2, where the black points belong to the subset and the white
points do not. So the text “INFINITE” in Figure 1.4(c) is a subset of R2
and therefore an element of P(R2). By that token, P(R2) contains a copy
of the page you are reading now.
Thus in addition to containing every imaginable function and every
imaginable black-and-white image, P(R2) also contains the full text of
every book that was ever written, those that are yet to be written and
those that will never be written. Inside of P(R2) is a detailed biography of
your life, from beginning to end, as well as the biographies of all of your
unborn descendants. It is startling that the five symbols used to write
P(R2) can express such an incomprehensibly large set.
Homework: Think about P(P(R2)).
Exercises for Section 1.4
A. Find the indicated sets.
1. P ¡©©a, bª,©cªª¢
7. P ¡©a, bª¢ × P ¡©0,1ª¢
2. P ¡©1,2,3,4ª¢
8. P ¡©1,2ª × ©3ª¢
3. P ¡©©;ª,5ª¢
9. P ¡©a, bª × ©0ª¢
4. P ¡©R,Qª¢
10. ©X ∈ P ¡©1,2,3ª¢ : |X | ≤ 1ª
5. P ¡P ¡©2ª¢¢
11. ©X ⊆ P ¡©1,2,3ª¢ : |X | ≤ 1ª
6. P ¡©1,2ª¢ × P ¡©3ª¢
12. ©X ∈ P ¡©1,2,3ª¢ : 2 ∈ X ª
B. Suppose that |A| = m and |B| = n. Find the following cardinalities.
13. |P(P(P(A)))|
17. ¯©
¯
X ∈ P(A) : |X | ≤ 1ª¯¯
14. |P(P(A))|
18. |P(A × P(B))|
15. |P(A × B)|
19. |P(P(P(A × ;)))|
16. |P(A) × P(B)|
20. ¯©
¯
X ⊆ P(A) : |X | ≤ 1ª¯¯
Union, Intersection, Difference
17
1.5 Union, Intersection, Difference
Just as numbers are combined with operations such as addition, subtrac-
tion and multiplication, there are various operations that can be applied to
sets. The Cartesian product (defined in Section 1.2) is one such operation;
given sets A and B, we can combine them with × to get a new set A × B.
Here are three new operations called union, intersection and difference.
Definition 1.5
Suppose A and B are sets.
The union of A and B is the set
A ∪ B = ©x : x ∈ A or x ∈ Bª.
The intersection of A and B is the set
A ∩ B = ©x : x ∈ A and x ∈ Bª.
The difference of A and B is the set
A − B = ©x : x ∈ A and x ∉ Bª.
In words, the union A ∪ B is the set of all things that are in A or in B
(or in both). The intersection A ∩ B is the set of all things in both A and B.