Page 147 - Discrete Mathematics and Its Applications

126 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

2
13. Use a Venn diagram to illustrate the set of all months of 33. Find A if
the year whose names do not contain the letter R in the a) A ={0, 1, 3}. b) A ={1, 2,a,b}.
set of all months of the year. 3
34. Find A if
14. Use a Venn diagram to illustrate the relationship A ⊆ B a) A ={a}. b) A ={0,a}.
and B ⊆ C.
35. How many different elements does A × B have if A has
15. Use a Venn diagram to illustrate the relationships A ⊂ B m elements and B has n elements?
and B ⊂ C.
36. How many different elements does A × B × C have if A
16. Use a Venn diagram to illustrate the relationships A ⊂ B has m elements, B has n elements, and C has p elements?
and A ⊂ C. n
37. How many different elements does A have when A has
17. Suppose that A, B, and C are sets such that A ⊆ B and m elements and n is a positive integer?
B ⊆ C. Show that A ⊆ C.
38. Show that A × B = B × A, when A and B are nonempty,
18. Find two sets A and B such that A ∈ B and A ⊆ B. unless A = B.
19. What is the cardinality of each of these sets? 39. Explain why A × B × C and (A × B) × C are not the
a) {a} b) {{a}} same.
c) {a, {a}} d) {a, {a}, {a, {a}}} 40. Explain why (A × B) × (C × D) and A × (B × C) ×
20. What is the cardinality of each of these sets? D are not the same.
41. Translate each of these quantifications into English and
a) ∅ b) {∅}
determine its truth value.
c) {∅, {∅}} d) {∅, {∅}, {∅, {∅}}}
2
2
21. Find the power set of each of these sets, where a and b a) ∀x∈R (x =−1) b) ∃x∈Z (x = 2)
2
2
are distinct elements. c) ∀x∈Z (x > 0) d) ∃x∈R (x = x)
42. Translate each of these quantifications into English and
a) {a} b) {a, b} c) {∅, {∅}}
determine its truth value.
22. Can you conclude that A = B if A and B are two sets 3
with the same power set? a) ∃x∈R (x =−1) b) ∃x∈Z (x + 1 >x)
2
c) ∀x∈Z (x − 1 ∈ Z) d) ∀x∈Z (x ∈ Z)
23. How many elements does each of these sets have where
a and b are distinct elements? 43. Find the truth set of each of these predicates where the
domain is the set of integers.
a) P({a, b, {a, b}}) 2 2
b) P({∅,a, {a}, {{a}}}) a) P(x): x < 3 b) Q(x): x >x
c) R(x):2x + 1 = 0
c) P(P(∅))
44. Find the truth set of each of these predicates where the
24. Determine whether each of these sets is the power set of
domain is the set of integers.
a set, where a and b are distinct elements.
3
2
a) P(x): x ≥ 1 b) Q(x): x = 2
a) ∅ b) {∅, {a}}
c) R(x): x< x 2
c) {∅, {a}, {∅,a}} d) {∅, {a}, {b}, {a, b}}
∗ 45. The defining property of an ordered pair is that two or-
25. Prove that P(A) ⊆ P(B) if and only if A ⊆ B.
dered pairs are equal if and only if their first elements
26. Show that if A ⊆ C and B ⊆ D, then A × B ⊆ C × D
are equal and their second elements are equal. Surpris-
27. Let A ={a, b, c, d} and B ={y, z}. Find ingly, instead of taking the ordered pair as a primitive con-
a) A × B. b) B × A. cept, we can construct ordered pairs using basic notions
28. What is the Cartesian product A × B, where A is the set from set theory. Show that if we define the ordered pair
of courses offered by the mathematics department at a (a, b) to be {{a}, {a, b}}, then (a, b) = (c, d) if and only
university and B is the set of mathematics professors at if a = c and b = d.[Hint: First show that {{a}, {a, b}} =
this university? Give an example of how this Cartesian {{c}, {c, d}} if and only if a = c and b = d.]
product can be used. ∗ 46. This exercise presents Russell’s paradox. Let S be the
29. What is the Cartesian product A × B × C, where A is set that contains a set x if the set x does not belong to
the set of all airlines and B and C are both the set of all itself, so that S ={x | x/∈ x}.
cities in the United States? Give an example of how this a) Show the assumption that S is a member of S leads to
Cartesian product can be used. a contradiction.
b) Show the assumption that S is not a member of S leads
30. Suppose that A × B =∅, where A and B are sets. What
to a contradiction.
can you conclude?
By parts (a) and (b) it follows that the set S cannot be de-
31. Let A be a set. Show that ∅× A = A × ∅=∅.
fined as it was. This paradox can be avoided by restricting
32. Let A ={a, b, c}, B ={x, y}, and C ={0, 1}. Find
the types of elements that sets can have.
a) A × B × C. b) C × B × A. ∗ 47. Describe a procedure for listing all the subsets of a finite
c) C × A × B. d) B × B × B. set.