shown {n ∈ Z : n | k} ⊆ ©n ∈ Z : n | k2ª.
■
5. If p and q are integers, then {pn : n ∈ N} ∩ {qn : n ∈ N} 6= ;.
Proof. Suppose p and q are integers. Consider the integer pq. Observe that
pq ∈ {pn : n ∈ N} and pq ∈ {qn : n ∈ N}, so pq ∈ {pn : n ∈ N} ∩ {qn : n ∈ N}. Therefore
{pn : n ∈ N} ∩ {qn : n ∈ N} 6= ;.
■
7. Suppose A, B and C are sets. If B ⊆ C, then A × B ⊆ A × C.
Proof. This is a conditional statement, and we’ll prove it with direct proof.
Suppose B ⊆ C. (Now we need to prove A × B ⊆ A × C.)
Suppose (a, b) ∈ A ×B. Then by definition of the Cartesian product we have a ∈ A
and b ∈ B. But since b ∈ B and B ⊆ C, we have b ∈ C. Since a ∈ A and b ∈ C, it
follows that (a, b) ∈ A × C. Now we’ve shown (a, b) ∈ A × B implies (a, b) ∈ A × C, so
A × B ⊆ A × C.
In summary, we’ve shown that if B ⊆ C, then A × B ⊆ A × C. This completes the
proof.
■
9. If A, B and C are sets then A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
Proof. We use the distributive law P ∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R) from page 50.
A ∩ (B ∪ C) = {x : x ∈ A ∧ x ∈ B ∪ C}
(def. of intersection)
= {x : x ∈ A ∧ (x ∈ B ∨ x ∈ C)}
(def. of union)
= ©x : ¡x ∈ A ∧ x ∈ B¢ ∨ ¡x ∈ A ∧ x ∈ C¢ª
(distributive law)
= {x : (x ∈ A ∩ B) ∨ (x ∈ A ∩ C)}
(def. of intersection)
= (A ∩ B) ∪ (A ∩ C)
(def. of union)
The proof is complete.
■
271
11. If A and B are sets in a universal set U, then A ∪ B = A ∩ B.
Proof. Just observe the following sequence of equalities.
A ∪ B
= U − (A ∪ B)
(def. of complement)
= {x : (x ∈ U) ∧ (x ∉ A ∪ B)}
(def. of −)
= {x : (x ∈ U)∧ ∼ (x ∈ A ∪ B)}
= {x : (x ∈ U)∧ ∼ ((x ∈ A) ∨ (x ∈ B))}
(def. of ∪)
= {x : (x ∈ U) ∧ (∼ (x ∈ A)∧ ∼ (x ∈ B))}
(DeMorgan)
= {x : (x ∈ U) ∧ (x ∉ A) ∧ (x ∉ B)}
= {x : (x ∈ U) ∧ (x ∈ U) ∧ (x ∉ A) ∧ (x ∉ B)}
(x ∈ U) = (x ∈ U) ∧ (x ∈ U)
= {x : ((x ∈ U) ∧ (x ∉ A)) ∧ ((x ∈ U) ∧ (x ∉ B))}
(regroup)
= {x : (x ∈ U) ∧ (x ∉ A)} ∩ {x : (x ∈ U) ∧ (x ∉ B)}
(def. of ∩)
= (U − A) ∩ (U − B)
(def. of −)
= A ∩ B
(def. of complement)
The proof is complete.
■
13. If A, B and C are sets, then A − (B ∪ C) = (A − B) ∩ (A − C).
Proof. Just observe the following sequence of equalities.
A − (B ∪ C) = {x : (x ∈ A) ∧ (x ∉ B ∪ C)}
(def. of −)
= {x : (x ∈ A)∧ ∼ (x ∈ B ∪ C)}
= {x : (x ∈ A)∧ ∼ ((x ∈ B) ∨ (x ∈ C))}
(def. of ∪)
= {x : (x ∈ A) ∧ (∼ (x ∈ B)∧ ∼ (x ∈ C))}
(DeMorgan)
= {x : (x ∈ A) ∧ (x ∉ B) ∧ (x ∉ C)}
= {x : (x ∈ A) ∧ (x ∈ A) ∧ (x ∉ B) ∧ (x ∉ C)}
(x ∈ A) = (x ∈ A) ∧ (x ∈ A)
= {x : ((x ∈ A) ∧ (x ∉ B)) ∧ ((x ∈ A) ∧ (x ∉ C))}
(regroup)
= {x : (x ∈ A) ∧ (x ∉ B)} ∩ {x : (x ∈ A) ∧ (x ∉ C)}
(def. of ∩)
= (A − B) ∩ (A − C)
(def. of −)
The proof is complete.
■
15. If A, B and C are sets, then (A ∩ B) − C = (A − C) ∩ (B − C).
Proof. Just observe the following sequence of equalities.
(A ∩ B) − C
= {x : (x ∈ A ∩ B) ∧ (x ∉ C)}
(def. of −)
= {x : (x ∈ A) ∧ (x ∈ B) ∧ (x ∉ C)}
(def. of ∩)
= {x : (x ∈ A) ∧ (x ∉ C) ∧ (x ∈ B) ∧ (x ∉ C)}
(regroup)
= {x : ((x ∈ A) ∧ (x ∉ C)) ∧ ((x ∈ B) ∧ (x ∉ C))}
(regroup)
= {x : (x ∈ A) ∧ (x ∉ C)} ∩ {x : (x ∈ B) ∧ (x ∉ C)}
(def. of ∩)
= (A − C) ∩ (B − C)
(def. of ∩)
The proof is complete.
■
17. If A, B and C are sets, then A × (B ∩ C) = (A × B) ∩ (A × C).
Proof. See Example 8.12.
■
272
Solutions
19. Prove that {9n : n ∈ Z} ⊆ {3n : n ∈ Z}, but {9n : n ∈ Z} 6= {3n : n ∈ Z}.
Proof. Suppose a ∈ {9n : n ∈ Z}. This means a = 9n for some integer n ∈ Z. Thus
a = 9n = (32)n = 32n. This shows a is an integer power of 3, so a ∈ {3n : n ∈ Z}.
Therefore a ∈ {9n : n ∈ Z} implies a ∈ {3n : n ∈ Z}, so {9n : n ∈ Z} ⊆ {3n : n ∈ Z}.
But notice {9n : n ∈ Z} 6= {3n : n ∈ Z} as 3 ∈ {3n : n ∈ Z}, but 3 ∉ {9n : n ∈ Z}.
■
21. Suppose A and B are sets. Prove A ⊆ B if and only if A − B = ;.
Proof. First we will prove that if A ⊆ B, then A − B = ;. Contrapositive proof is
used. Suppose that A − B 6= ;. Thus there is an element a ∈ A − B, which means
a ∈ A but a ∉ B. Since not every element of A is in B, we have A 6⊆ B.
Conversely, we will prove that if A − B = ;, then A ⊆ B. Again, contrapositive
proof is used. Suppose A 6⊆ B. This means that it is not the case that every
element of A is an element of B, so there is an element a ∈ A with a ∉ B.
Therefore we have a ∈ A − B, so A − B 6= ;.
■
23.
For each a ∈ R, let Aa = ©(x, a(x2 − 1)) ∈ R2 : x ∈ Rª. Prove that
Aa = {(−1,0),(1,0))}.
a∈R
Proof. First we will show that {(−1,0),(1,0))} ⊆ Aa. Notice that for any a ∈ R,
a∈R
we have (−1, 0) ∈ Aa because Aa contains the ordered pair (−1, a((−1)2 −1) = (−1, 0).
Similarly (1, 0) ∈ Aa. Thus each element of {(−1, 0), (1, 0))} belongs to every set
A
a, so every element of
Aa, so {(−1,0),(1,0))} ⊆ Aa.
a∈R
a∈R
Now we will show
Aa ⊆ {(−1,0),(1,0))}. Suppose (c, d) ∈ Aa. This means
a∈R
a∈R
(c, d) is in every set Aa. In particular (c, d) ∈ A0 = ©(x,0(x2 − 1)) : x ∈ Rª = {(x,0) : x ∈ R}.
It follows that d = 0. Then also we have (c, d) = (c, 0) ∈ A1 = ©(x, 1(x2 − 1)) : x ∈ Rª =
©(x, x2 − 1) : x ∈ Rª. Therefore (c,0) has the form (c, c2 − 1), that is (c,0) = (c, c2 − 1).
From this we get c2 − 1 = 0, so c = ±1. Therefore (c, d) = (1, 0) or (c, d) = (−1, 0),
so (c, d) ∈ {(−1, 0), (1, 0))}. This completes the demonstration that (c, d) ∈ Aa
a∈R
implies (c, d) ∈ {(−1, 0), (1, 0))}, so it follows that
Aa ⊆ {(−1,0),(1,0))}.
a∈R
Now it’s been shown that {(−1, 0), (1, 0))} ⊆ Aa and
Aa ⊆ {(−1,0),(1,0))}, so it
a∈R
a∈R
follows that
Aa = {(−1,0),(1,0))}.
■
a∈R
25. Suppo
se A, B, C and D are sets. Prove that (A × B) ∪ (C × D) ⊆ (A ∪ C) × (B ∪ D).
Proof. Suppose (a, b) ∈ (A × B) ∪ (C × D).
By definition of union, this means (a, b) ∈ (A × B) or (a, b) ∈ (C × D).
We examine these two cases individually.
Case 1. Suppose (a, b) ∈ (A × B). By definition of ×, it follows that a ∈ A and
b ∈ B. From this, it follows from the definition of ∪ that a ∈ A ∪ C and b ∈ B ∪ D.
Again from the definition of ×, we get (a, b) ∈ (A ∪ C) × (B ∪ D).
273
Case 2. Suppose (a, b) ∈ (C × D). By definition of ×, it follows that a ∈ C and
b ∈ D. From this, it follows from the definition of ∪ that a ∈ A ∪ C and b ∈ B ∪ D.
Again from the definition of ×, we get (a, b) ∈ (A ∪ C) × (B ∪ D).
In either case, we obtained (a, b) ∈ (A ∪ C) × (B ∪ D),
so we’ve proved that (a, b) ∈ (A × B) ∪ (C × D) implies (a, b) ∈ (A ∪ C) × (B ∪ D).
Therefore (A × B) ∪ (C × D) ⊆ (A ∪ C) × (B ∪ D).
■
27. Prove {12a + 4b : a, b ∈ Z} = {4c : c ∈ Z}.
Proof. First we show {12a + 4b : a, b ∈ Z} ⊆ {4c : c ∈ Z}. Suppose x ∈ {12a + 4b : a, b ∈ Z}.
Then x = 12a + 4b for some integers a and b. From this we get x = 4(3a + b), so
x = 4c where c is the integer 3a+b. Consequently x ∈ {4c : c ∈ Z}. This establishes
that {12a + 4b : a, b ∈ Z} ⊆ {4c : c ∈ Z}.
Next we show {4c : c ∈ Z} ⊆ {12a + 4b : a, b ∈ Z}. Suppose x ∈ {4c : c ∈ Z}. Then x = 4c
for some c ∈ Z. Thus x = (12 + 4(−2))c = 12c + 4(−2c), and since c and −2c are
integers we have x ∈ {12a + 4b : a, b ∈ Z}.
This proves that {12a + 4b : a, b ∈ Z} = {4c : c ∈ Z}.
■
29. Suppose A 6= ;. Prove that A × B ⊆ A × C, if and only if B ⊆ C.
Proof. First we will prove that if A×B ⊆ A×C, then B ⊆ C. Using contrapositive,
suppose that B 6⊆ C. This means there is an element b ∈ B with b ∉ C. Since
A 6= ;, there exists an element a ∈ A. Now consider the ordered pair (a, b). Note
that (a, b) ∈ A × B, but (a, b) 6∈ A × C. This means A × B 6⊆ A × C.
Conversely, we will now show that if B ⊆ C, then A × B ⊆ A × C. We use direct
proof. Suppose B ⊆ C. Assume that (a, b) ∈ A × B. This means a ∈ A and b ∈ B.
But, as B ⊆ C, we also have b ∈ C. From a ∈ A and b ∈ C, we get (a, b) ∈ A × C.
We’ve now shown (a, b) ∈ A × B implies (a, b) ∈ A × C, so A × B ⊆ A × C.
■
31. Suppose B 6= ; and A × B ⊆ B × C. Prove A ⊆ C.
Proof. Suppose B 6= ; and A × B ⊆ B × C. In what follows, we show that A ⊆ C.
Let x ∈ A. Because B is not empty, it contains some element b. Observe that
(x, b) ∈ A × B. But as A × B ⊆ B × C, we also have (x, b) ∈ B × C, so, in particular,
x ∈ B. As x ∈ A and x ∈ B, we have (x, x) ∈ A × B. But as A × B ⊆ B × C, it follows
that (x, x) ∈ B × C. This implies x ∈ C.
Now we’ve shown x ∈ A implies x ∈ C, so A ⊆ C.
■
Chapter 9 Exercises
1. If x, y ∈ R, then |x + y| = |x| + |y|.
This is false.
Disproof: Here is a counterexample: Let x = 1 and y = −1. Then |x + y| = 0 and
|x| + |y| = 2, so it’s not true that |x + y| = |x| + |y|.
274
Solutions
3. If n ∈ Z and n5 − n is even, then n is even.
This is false.
Disproof: Here is a counterexample: Let n = 3. Then n5 − n = 35 − 3 = 240, but
n is not even.
5. If A, B, C and D are sets, then (A × B) ∪ (C × D) = (A ∪ C) × (B ∪ D).
This is false.
Disproof: Here is a counterexample: Let A = {1,2}, B = {1,2}, C = {2,3} and
D = {2,3}. Then (A ×B)∪(C × D) = {(1,1),(1,2),(2,1),(2,2)}∪{(2,2),(2,3),(3,2),(3,3)} =
{(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 2), (3, 3)} . Also (A ∪ C) × (B ∪ D) = {1,2,3} × {1,2,3}=
{(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)}, so you can see that (A × B) ∪
(C × D) 6= (A ∪ C) × (B ∪ D).
7. If A, B and C are sets, and A × C = B × C, then A = B.
This is false.
Disproof: Here is a counterexample: Let A = {1}, B = {2} and C = ;. Then
A × C = B × C = ;, but A 6= B.
9. If A and B are sets, then P(A) − P(B) ⊆ P(A − B).
This is false.
Disproof: Here is a counterexample: Let A = {1,2} and B = {1}. Then P(A) −
P(B) = {;,{1},{2},{1,2}}−{;,{1}} = {{2},{1,2}}. Also P(A −B) = P({2}) = {;,{2}}. In
this example we have P(A) − P(B) 6⊆ P(A − B).
11. If a, b ∈ N, then a + b < ab.
This is false.
Disproof: Here is a counterexample: Let a = 1 and b = 1. Then a + b = 2 and
ab = 1, so it’s not true that a + b < ab.
13. There exists a set X for which R ⊆ X and ; ∈ X . This is true.
Proof. Simply let X = R ∪ {;}. If x ∈ R, then x ∈ R ∪ {;} = X , so R ⊆ X . Likewise,
; ∈ R ∪ {;} = X because ; ∈ {;}.
■
15. Every odd integer is the sum of three odd integers. This is true.
Proof. Suppose n is odd. Then n = n + 1 + (−1), and therefore n is the sum of
three odd integers.
■
17. For all sets A and B, if A − B = ;, then B 6= ;.
This is false.
Disproof: Here is a counterexample: Just let A = ; and B = ;. Then A − B = ;,
but it’s not true that B 6= ;.
19. For every r, s ∈ Q with r < s, there is an irrational number u for which r < u < s.
This is true.
p
Proof. (Direct) Suppose r, s ∈ Q with r < s. Consider the number u = r + 2 s−r
2 .
In what follows we will show that u is irrational and r < u < s. Certainly since
275
p
p
s − r is positive, it follows that r < r + 2 s−r
2
2
= u. Also, since
< 2 we have
p s − r
s − r
u = r + 2
< r + 2
= s,
2
2
and therefore u < s. Thus we can conclude r < u < s.
Now we just need to show that u is irrational. Suppose for the sake of contra-
diction that u is rational. Then u = ab for some integers a and b. Since r and s
are rational, we have r = cd and s = ef for some c, d, e, f ∈ Z. Now we have
p s − r
u
=
r + 2 2
e
a
c
p f − cd
=
+ 2
b
d
2
ad − bc
p ed − c f
=
2
bd
2d f
(ad − bc)2d f
p
=
2
bd(ed − c f )
p
p
This expresses
2 as a quotient of two integers, so 2 is rational, a contradiction.
Thus u is irrational.
In summary, we have produced an irrational number u with r < u < s, so the
proof is complete.
■
21. There exist two prime numbers p and q for which p − q = 97.
This statement is false.
Disproof: Suppose for the sake of contradiction
that this is true. Let p and
q be prime numbers for which p − q = 97. Now, since their difference is odd, p
and q must have opposite parity, so one of p and q is even and the other is
odd. But there exists only one even prime number (namely 2), so either p = 2
or q = 2. If p = 2, then p − q = 97 implies q = 2 − 97 = −95, which is not prime.
On the other hand if q = 2, then p − q = 97 implies p = 99, but that’s not prime
either. Thus one of p or q is not prime, a contradiction.
23. If x, y ∈ R and x3 < y3, then x < y. This is true.
Proof. (Contrapositive) Suppose x ≥ y. We need to show x3 ≥ y3.
Case 1. Suppose x and y have opposite signs, that is one of x and y is positive
and the other is negative. Then since x ≥ y, x is positive and y is negative.
Then, since the powers are odd, x3 is positive and y3 is negative, so x3 ≥ y3.
Case 2. Suppose x and y do not have opposite signs. Then x2 + xy + y2 ≥ 0 and
also x − y ≥ 0 because x ≥ y. Thus we have x3 − y3 = (x − y)(x2 + x y + y2) ≥ 0. From
this we get x3 − y3 ≥ 0, so x3 ≥ y3.
In either case we have x3 ≥ y3.
■
276
Solutions
25. For all a, b, c ∈ Z, if a | bc, then a | b or a | c.
This is false.
Disproof: Let a = 6, b = 3 and c = 4. Note that a | bc, but a - b and a - c.
27. The equation x2 = 2x has three real solutions.
Proof. By inspection, the numbers x = 2 and x = 4 are two solutions of this
equation. But there is a third solution. Let m be the real number for which
m2m = 12 . Then negative number x = −2m is a solution, as follows.
Ã
1 !2
µ m2m ¶2
1
x2 = (−2m)2 = 4m2 = 4
= 4
2
=
= 2−2m = 2x.
2m
2m
22m
Therefore we have three solutions 2, 4 and m.
■
29. If x, y ∈ R and |x + y| = |x − y|, then y = 0.
This is false.
Disproof: Let x = 0 and y = 1. Then |x + y| = |x − y|, but y = 1.
31. No number appears in Pascal’s triangle more than four times.
Disproof:
¡ 10 ¢
¢
¢
The number 120 appears six times. Check that
3
= ¡ 10
7
= ¡ 16
2
=
¡ 16 ¢
¢
¢
14 = ¡ 120
1
= ¡ 120
119 = 120.
33. Suppose f (x) = a0 + a1x + a2x2 + ··· + anxn is a polynomial of degree 1 or greater,
and for which each coefficient ai is in N. Then there is an n ∈ N for which the
Book of Proof Page 39
