248
Sets, Combinatorics, and Probability
65. Which of the following statements are true for all sets A, B, and C?
a. A c (B × C ) = (A c B) × (A c C )
b. A × (B d C ) = (A × B) d (A × C )
c. A × [ = [
66. Which of the following statements are true for all sets A, B, and C?
a. ℘(A) × ℘(A) = ℘(A
2
)
b. A × (B × C ) = (A × B) × C
c. ℘(A × B) = ℘(A) × ℘(B)
67. For each of the following statements, find general conditions on sets A and B to make the statement true:
a. A c B = A
c. A c [ = [
e. A c B # A d B
b. A d B = A
d. B − A = [
f. A × B = B × A
68. For any finite set S, 0 S 0 denotes the number of elements in S. If 0 A 0 = 3 and 0 B 0 = 4, find
a. 0 A × B 0
b. 0 A
2
0
c. 0 B
2
0
d. the maximum possible value for 0 A d B 0
e. the minimum possible value for 0 A c B 0
69. Prove that (A d B) # A where A and B are arbitrary sets.
70. Prove that A # (A c B) where A and B are arbitrary sets.
71. Prove that ℘(A) d ℘(B) = ℘(A d B) where A and B are arbitrary sets.
72. Prove that ℘(A) c ℘(B) # ℘(A c B) where A and B are arbitrary sets.
73. Prove that if A c B = A − B, then B = [. (Hint: Do a proof by contradiction.)
74. Prove that if (A − B) c (B − A) = A c B, then A d B = [. (Hint: Do a proof by contradiction.)
75. Prove that if C # B − A, then A d C = [.
76. Prove that if (A − B) c B = A, then B # A.
77. Prove that A # B if and only if A d B′ = [.
78. Prove that (A d B) c C = A d (B c C ) if and only if C # A.
Exercises 79 and 80 refer to a binary operation on sets called the symmetric difference, which is defined by
A ! B = (A − B) c (B − A).
79. a. Draw a Venn diagram to illustrate A ! B.
b. For A = {3, 5, 7, 9} and B = {2, 3, 4, 5, 6}, what is A ! B?
c. Prove that A ! B = (A c B) − (A d B) for arbitrary sets A and B.
80. a. For an arbitrary set A, what is A ! A? What is [ ! A?
b. Prove that A ! B = B ! A for arbitrary sets A and B.
c. For any sets A, B, and C, prove that (A ! B) ! C = A ! (B ! C ).
81. Verify the basic set identities on page 234 by showing set inclusion in each direction. (We have already
done 3a and 4a.)
82. A and B are subsets of a set S. Prove the following set identities by showing set inclusion in each direction.
a. (A c B)′ = A′ d B′
b. (A d B)′ = A′ c B′
f De Morgan’s laws
Sets, Combinatorics, and Probability
65. Which of the following statements are true for all sets A, B, and C?
a. A c (B × C ) = (A c B) × (A c C )
b. A × (B d C ) = (A × B) d (A × C )
c. A × [ = [
66. Which of the following statements are true for all sets A, B, and C?
a. ℘(A) × ℘(A) = ℘(A
2
)
b. A × (B × C ) = (A × B) × C
c. ℘(A × B) = ℘(A) × ℘(B)
67. For each of the following statements, find general conditions on sets A and B to make the statement true:
a. A c B = A
c. A c [ = [
e. A c B # A d B
b. A d B = A
d. B − A = [
f. A × B = B × A
68. For any finite set S, 0 S 0 denotes the number of elements in S. If 0 A 0 = 3 and 0 B 0 = 4, find
a. 0 A × B 0
b. 0 A
2
0
c. 0 B
2
0
d. the maximum possible value for 0 A d B 0
e. the minimum possible value for 0 A c B 0
69. Prove that (A d B) # A where A and B are arbitrary sets.
70. Prove that A # (A c B) where A and B are arbitrary sets.
71. Prove that ℘(A) d ℘(B) = ℘(A d B) where A and B are arbitrary sets.
72. Prove that ℘(A) c ℘(B) # ℘(A c B) where A and B are arbitrary sets.
73. Prove that if A c B = A − B, then B = [. (Hint: Do a proof by contradiction.)
74. Prove that if (A − B) c (B − A) = A c B, then A d B = [. (Hint: Do a proof by contradiction.)
75. Prove that if C # B − A, then A d C = [.
76. Prove that if (A − B) c B = A, then B # A.
77. Prove that A # B if and only if A d B′ = [.
78. Prove that (A d B) c C = A d (B c C ) if and only if C # A.
Exercises 79 and 80 refer to a binary operation on sets called the symmetric difference, which is defined by
A ! B = (A − B) c (B − A).
79. a. Draw a Venn diagram to illustrate A ! B.
b. For A = {3, 5, 7, 9} and B = {2, 3, 4, 5, 6}, what is A ! B?
c. Prove that A ! B = (A c B) − (A d B) for arbitrary sets A and B.
80. a. For an arbitrary set A, what is A ! A? What is [ ! A?
b. Prove that A ! B = B ! A for arbitrary sets A and B.
c. For any sets A, B, and C, prove that (A ! B) ! C = A ! (B ! C ).
81. Verify the basic set identities on page 234 by showing set inclusion in each direction. (We have already
done 3a and 4a.)
82. A and B are subsets of a set S. Prove the following set identities by showing set inclusion in each direction.
a. (A c B)′ = A′ d B′
b. (A d B)′ = A′ c B′
f De Morgan’s laws