Book of Proof
Page 34
hypothesis. In essence he proved that the continuum hypothesis cannot be
proved.
Taken together, Gödel and Cohens’ results mean that the standard
axioms of mathematics cannot “decide” whether the continuum hypothesis
is true or false; that no logical conflict can arise from either asserting or
denying the continuum hypothesis. We are free to either accept it as true
or accept it as false, and the two choices lead to different—but equally
consistent—versions of set theory.
238
Cardinality of Sets
On the face of it, this seems to undermine the foundation of logic, and
everything we have done in this book. The continuum hypothesis should
be a statement – it should be either true or false. How could it be both?
Here is an analogy that may help make sense of this. Consider the
number systems Zn. What if we asked whether [2] = [0] is true or false? Of
course the answer depends on n. The expression [2] = [0] is true in Z2 and
false in Z3. Moreover, if we assert that [2] = [0] is true, we are logically
forced to the conclusion that this is taking place in the system Z2. If we
assert that [2] = [0] is false, then we are dealing with some other Zn. The
fact that [2] = [0] can be either true or false does not necessarily mean
that there is some inherent inconsistency within the individual number
systems Zn. The equation [2] = [0] is a true statement in the “universe” of
Z2 and a false statement in the universe of (say) Z3.
It is the same with the continuum hypothesis. Saying it’s true leads to
one system of set theory. Saying it’s false leads to some other system of set
theory. Gödel and Cohens’ discoveries mean that these two types of set
theory, although different, are equally consistent and valid mathematical
universes.
So what should you believe?
Fortunately, it does not make much
difference, because most important mathematical results do not hinge on
the continuum hypothesis. (They are true in both universes.) Unless you
undertake a deep study of the foundations of mathematics, you will be fine
accepting the continuum hypothesis as true. Most mathematicians are
agnostics on this issue, but they tend to prefer the version of set theory in
which the continuum hypothesis holds.
The situation with the continuum hypothesis is a testament to the
immense complexity of mathematics. It is a reminder of the importance
of rigor and careful, systematic methods of reasoning that begin with the
ideas introduced in this book.
Exercises for Section 13.4
1. Show that if A ⊆ B and there is an injection g : B → A, then |A| = |B|.
2. Show that |R2| = |R|. Suggestion: Begin by showing |(0,1) × (0,1)| = |(0,1)|.
3. Let F be the set of all functions N → ©0,1ª. Show that |R| = |F |.
4. Let F be the set of all functions R → ©0,1ª. Show that |R| < |F |.
5. Consider the subset B = ©(x, y) : x2 + y2 ≤ 1ª ⊆ R2. Show that |B| = |R2|.
6. Show that |P(N × N)| = |P(N)|.
7. Prove or disprove: If there is a injection f : A → B and a surjection g : A → B,
then there is a bijection h : A → B.
Conclusion
f you have internalized the ideas in this book, then you have a set
I of rhetorical tools for deciphering and communicating mathematics.
These tools are indispensable at any level. But of course it takes more
than mere tools to build something. Planning, creativity, inspiration, skill,
talent, intuition, passion and persistence are also vitally important. It
is safe to say that if you have come this far, then you probably possess a
sufficient measure of these traits.
The quest to understand mathematics has no end, but you are well
equipped for the journey. It is my hope that the things you have learned
from this book will lead you to a higher plane of understanding, creativity
and expression.
Good luck and best wishes.
R.H.
Solutions
Chapter 1 Exercises
Section 1.1
1. {5x − 1 : x ∈ Z} = {... − 11,−6,−1,4,9,14,19,24,29,...}
3. {x ∈ Z : −2 ≤ x < 7} = {−2,−1,0,1,2,3,4,5,6}
p p
5. ©x ∈ R : x2 = 3ª = ©− 3, 3ª
7. ©x ∈ R : x2 + 5x = −6ª = {−2,−3}
9. {x ∈ R : sin π x = 0} = {...,−2,−1,0,1,2,3,4,...} = Z
11. {x ∈ Z : |x| < 5} = {−4,−3,−2,−1,0,1,2,3,4}
13. {x ∈ Z : |6x| < 5} = {0}
15. {5a + 2b : a, b ∈ Z} = {...,−2,−1,0,1,2,3,...} = Z
17. {2, 4, 8, 16, 32, 64 . . .} = {2x : x ∈ N}
19. {. . . , −6,−3,0,3,6,9,12,15,...} = {3x : x ∈ Z}
21. {0, 1, 4, 9, 16, 25, 36, . . .} = ©x2 : x ∈ Zª
23. {3, 4, 5, 6, 7, 8} = {x ∈ Z : 3 ≤ x ≤ 8} = {x ∈ N : 3 ≤ x ≤ 8}
25. ©. . . , 1 , 1 , 1 , 1, 2, 4, 8, . . .ª
8 4 2
= {2n : n ∈ Z}n
o
27. ©. . . , − π,− π ,0, π , π, 3 π ,2 π, 5 π ,...ª
k π : k
2
2
2
2
=
2
∈ Z
29. |{{1},{2,{3,4}},;}| = 3
33. |{x ∈ Z : |x| < 10}| = 19
37. |©x ∈ N : x2 < 0ª| = 0
31. |{{{1},{2,{3,4}},;}}| = 1 35. |©x ∈ Z : x2 < 10ª| = 7
39. {(x, y) : x ∈ [1,2], y ∈ [1,2]}
43. {(x, y) : |x| = 2, y ∈ [0,1]}
2
2
1
1
−3 −2 −1
1
2
3
−3 −2 −1
1
2
3
−1
−1
−2
−2
41. {(x, y) : x ∈ [−1,1], y = 1}
45. ©(x, y) : x, y ∈ R, x2 + y2 = 1ª
2
2
1
1
−3 −2 −1
1
2
3
−3 −2 −1
1
2
3
−1
−1
−2
−2
241
47. ©(x, y) : x, y ∈ R, y ≥ x2 − 1ª
49. {(x, x + y) : x ∈ R, y ∈ Z}
3
3
2
2
1
1
−3 −2 −1
1
2
3
−3 −2 −1
1
2
3
−1
−1
−2
−2
−3
−3
51. {(x, y) ∈ R2 : (y − x)(y + x) = 0}
3
2
1
−3 −2 −1
1
2
3
−1
−2
−3
Section 1.2
1. Suppose A = {1,2,3,4} and B = {a, c}.
(a) A × B = {(1, a), (1, c), (2, a), (2, c), (3, a), (3, c), (4, a), (4, c)}
(b) B × A = {(a, 1), (a, 2), (a, 3), (a, 4), (c, 1), (c, 2), (c, 3), (c, 4)}
(c) A × A = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4),
(3, 1), (3, 2), (3, 3), (3, 4), (4, 1), (4, 2), (4, 3), (4, 4)}
(d) B × B = {(a, a), (a, c), (c, a), (c, c)}
(e) ; × B = {(a, b) : a ∈ ;, b ∈ B} = ; (There are no ordered pairs (a, b) with a ∈ ;.)
(f) (A × B) × B =
{((1, a), a), ((1, c), a), ((2, a), a), ((2, c), a), ((3, a), a), ((3, c), a), ((4, a), a), ((4, c), a),
((1, a), c), ((1, c), c), ((2, a), c), ((2, c), c), ((3, a), c), ((3, c), c), ((4, a), c), ((4, c), c)}
(g) A × (B × B) =
©(1,(a, a)),(1,(a, c)),(1,(c, a)),(1,(c, c)),
(2, (a, a)), (2, (a, c)), (2, (c, a)), (2, (c, c)),
(3, (a, a)), (3, (a, c)), (3, (c, a)), (3, (c, c)),
(4, (a, a)), (4, (a, c)), (4, (c, a)), (4, (c, c))ª
(h) B3 = {(a, a, a), (a, a, c), (a, c, a), (a, c, c), (c, a, a), (c, a, c), (c, c, a), (c, c, c)}
p
p
p
p
p
p
3. ©x ∈ R : x2 = 2ª × {a, c, e} = ©(− 2, a),( 2, a),(− 2, c),( 2, c),(− 2, e),( 2, e)ª
p
p
p
p
5. ©x ∈ R : x2 = 2ª × {x ∈ R : |x| = 2} = ©(− 2,−2),( 2,2),(− 2,2),( 2,−2)ª
7. {;} × {0,;} × {0,1} = {(;,0,0),(;,0,1),(;,;,0),(;,;,1)}
242
Solutions
Sketch the following Cartesian products on the x- y plane.
9. {1, 2, 3} × {−1,0,1}
15. {1} × [0,1]
2
2
1
1
−3 −2 −1
1
2
3
−3 −2 −1
1
2
3
−1
−1
−2
−2
11. [0, 1] × [0,1]
17. N × Z
2
2
1
1
−3 −2 −1
1
2
3
−3 −2 −1
1
2
3
−1
−1
−2
−2
13. {1, 1.5, 2} × [1,2]
19. [0, 1] × [0,1] × [0,1]
2
2
1
1
−3 −2 −1
1
2
3
−3 −2 −1
1
2
3
−1
−1
−2
−2
Section 1.3
A. List all the subsets of the following sets.
1. The subsets of {1,2,3,4} are: {}, {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4},
{3, 4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}.
3. The subsets of {{R}} are: {} and {{R}}.
5. The subsets of {;} are {} and {;}.
7. The subsets of {R,{Q,N}} are {}, {R},{{Q,N}}, {R,{Q,N}}.
B. Write out the following sets by listing their elements between braces.
9. ©X : X ⊆ {3,2, a} and |X | = 2ª = {{3,2},{3, a},{2, a}}
11. ©X : X ⊆ {3,2, a} and |X | = 4ª = {} = ;
C. Decide if the following statements are true or false.
13. R3 ⊆ R3 is true because any set is a subset of itself.
15. ©(x, y) : x − 1 = 0ª ⊆ ©(x, y) : x2 − x = 0ª. This is true. (The even-numbered ones
are both false. You have to explain why.)
243
Section 1.4
A. Find the indicated sets.
1. P({{a, b},{c}}) = {;,{{a, b}},{{c}},{{a, b},{c}}}
3. P({{;},5}) = {;,{{;}},{5},{{;},5}}
5. P(P({2})) = {;,{;},{{2}},{;,{2}}}
7. P({a, b}) × P({0,1}) =
©
(;,;),
(;,{0}),
(;,{1}),
(;,{0,1}),
({a} , ;),
({a} , {0}),
({a} , {1}),
({a} , {0, 1}),
({b} , ;),
({b} , {0}),
({b} , {1}),
({b} , {0, 1}),
({a, b} , ;), ({a, b},{0}), ({a, b},{1}), ({a, b},{0,1}) ª
9. P({a, b} × {0}) = {;,{(a,0)},{(b,0)},{(a,0),(b,0)}}
11. {X ⊆ P({1,2,3}) : |X | ≤ 1} =
{;,{;},{{1}},{{2}},{{3}},{{1,2}},{{1,3}},{{2,3}},{{1,2,3}}}
B. Suppose that |A| = m and |B| = n. Find the following cardinalities.
³2(2m)´
13. |P(P(P(A)))| = 2
15. |P(A × B)| = 2mn
17. |{X ∈ P(A) : |X | ≤ 1}| = m + 1
19. |P(P(P(A × ;)))| = |P(P(P(;)))| = 4
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 = {1,3,4,5,6,7,8,9}
(f) A ∩ C = {4}
(b) A ∩ B = {4,6}
(g) B ∩ C = {5,8,4}
(c) A − B = {3,7,1,9}
(h) B
(d) A
∪ C = {5, 6, 8, 4}
− C = {3, 6, 7, 1, 9}
(e) B − A = {5,8}
(i) C − B = ;
3. Suppose A = {0,1} and B = {1,2}. Find:
(a) (A × B) ∩ (B × B) = {(1,1),(1,2)}
(b) (A × B) ∪ (B × B) = {(0,1),(0,2),(1,1),(1,2),(2,1),(2,2)}
(c) (A × B) − (B × B) = {(0,1),(0,2)}
(f) P(A) ∩ P(B) = {;,{1}}
(d) (A ∩ B) × A = {(1,0),(1,1)}
(g) P(A) − P(B) = {{0},{0,1}}
(e) (A × B) ∩ B = ;
(h) P(A ∩ B) = {{},{1}}
(i) ©;,{(0,1)},{(0,2)},{(1,1)},{(1,2)},{(0,1),(0,2)},{(0,1),(1,1)},{(0,1),(1,2)},{(0,2),(1,1)},
{(0, 2), (1, 2)}, {(1, 1), (1, 2)}, {(0, 2), (1, 1), (1, 2)}, {(0, 1), (1, 1), (1, 2)}, {(0, 1), (0, 2), (1, 2)},
{(0, 1), (0, 2), (1, 1)}, {(0, 1), (0, 2), (1, 1), (1, 2)}ª
244
Solutions
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 Section 1.2.)
4
4
4
4
4
Y
Y − X
3
3
3
3
3
X ∪ Y
2
2
2
2
2
X
X ∩ Y
X − Y
1
1
1
1
1
1
2
3
4
1
2
3
4
1
2
3
4
1
2
3
4
1
2
3
4
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 .
2
2
2
2
2
Y
X ∪ Y
X ∩ Y
X − Y
Y − X
X 1
1
1
1
1
−2 −1
1
2
−2 −1
1
2
−2 −1
1
2
−2 −1
1
2
−2 −1
1
2
−1
−1
−1
−1
−1
−2
−2
−2
−2
−2
9. The first statement is true. (A picture should convince you; draw one if
necessary.) The second statement is false: Notice for instance that (0.5, 0.5) is
in the right-hand set, but not the left-hand set.
Section 1.6
1. Suppose A = {4,3,6,7,1,9} and B = {5,6,8,4} have universal set U = {n ∈ Z : 0 ≤ n ≤ 10}.
(a) A = {0,2,5,8,10}
(f) A − B = {4,6}
(b) B = {0,1,2,3,7,9,10}
(g) A − B = {5,8}
(c) A ∩ A = ;
(h) A ∩ B = {5,8}
(d) A ∪ A = {0,1,2,3,4,5,6,7,8,9,10} = U
(e) A − A = A
(i) A ∩ B = {0,1,2,3,4,6,7,9,10}
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]).
3
3
3
2
2
2
X
1
1
1
X
−1
1
2
3
−1
1
2
3
−1
1
2
3
X
−1
−1
−1
∩ ([0, 2] × [0, 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 .
245
3
3
2
2
X
1
X
1
A
U
1 2 3
1 2 3
A (shaded)
Solution of 1.6, #5.
Solution of 1.7, #1.
Section 1.7
1. Draw a Venn diagram for A. (Solution above right)
3. Draw a Venn diagram for (A − B) ∩ C.
Scratch work is shown on the right. The
set A − B is indicated with vertical shading.
C
C
The set C is indicated with horizontal shad-
ing. The intersection of A − B and C is thus
the overlapping region that is shaded with
both vertical and horizontal lines. The final
answer is drawn on the far right, where the
A
B
A
B
set (A − B) ∩ C is shaded in gray.
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)?
If you do the drawings carefully, you will find
C
that your Venn diagrams are the same for both
A ∪ (B ∩ C) and (A ∪ B) ∩ (A ∪ C). Each looks as
illustrated on the right. Based on this, we are
inclined to say that the equation A ∪ (B ∩ C) =
(A ∪ B) ∩ (A ∪ C) holds for all sets A, B and C.
A
B
7. Suppose sets A and B are in a universal set U. Draw Venn diagrams for A ∩ B