CS2336 Discrete Mathematics
Homework 5
Exam 3: January 10, 2022 (10:10–12:00)
1. Determine whether each of these pairs of sets are equal.
(a) {1, 3, 3, 3, 5, 5, 5, 5, 5}, {5, 3, 1}
(b) {{1}}, {1, {1}}
(c) ∅, {∅}
2. Let A = {1, {{1}}, {{2}}}. Which of the following statements are true?
(a) 1 ∈ A
(b) {1} ∈ A
(c) {1} ⊆ A
(d) {{1}} ⊆ A
(e) {{2}} ⊂ A
(f) {{1}, {2}} ⊂ A
3. Let A = {∅, {∅}}. Determine whether each of the following statements is true or false.
(a) ∅ ∈ 2A
(b) ∅ ⊆ 2A
(c) {∅} ⊆ 2A
(d) {∅} ⊆ A
(e) {∅} ∈ 2A
(f) {∅} ∈ A
(g) {{∅}} ⊆ 2A
(h) {{∅}} ⊆ A
(i) {{∅}} ∈ 2A
(j) {{∅}} ∈ A
4. A survey of 150 college students reveals that 83 own cars, 97 own bikes, 28 own motorcycles,
53 own a car and a bike, 14 own a car and a motorcycle, 7 own a bike and a motorcycle
and 2 own all three. How many students own a bike and nothing else?
5. For two sets A and B, we use A − B to denote A ∩ B. Find the sets A and B if A − B =
{1, 5, 7, 8}, B − A = {2, 10}, and A ∩ B = {3, 6, 9}.
6. For each of the following lists of integers, provide a simple formula or rule that generates
the terms of an integer sequence that begins with the given list. Assuming that your
formula or rule is correct, determine the next three terms of the sequence.
(a) 3, 6, 11, 18, 27, 38, 51, 66, 83, 102, ...
1
(b) 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, ...
(c) 0, 2, 8, 26, 80, 242, 728, 2186, 6560, 19682, ...
(d) 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, ...
7. Show that the set R of real numbers and the set R+ of positive real numbers have the same
cardinality. (That is, give a one-to-one correspondence between the items in the two sets.)
8. After learning the diagonalization technique, Peter has come up with the following proof,
showing that the set
X = { x | x ∈ (0, 1) and x has k decimal places and k ∈ N }
is uncountable:
We prove this by contradiction. Assume to the contrary that there is a one-to-one
correspondence between items in X and items in N. Then, we can list the items
in X one by one, say x1 , x2 , x3 , . . .. Now, consider the number x such that its
digit in the first decimal place is different from x1 , its digit in the second decimal
place is different from x2 , and in general, its digit in the jth decimal palce is
different from xj for all j. Then, x is not listed by the correspondence, and a
contradiction occurs as desired.
However, each number in X is a rational number; for instance, 0.33215 = 33215/100000.
Thus, X ⊆ Q (where Q is countable), which implies X must be countable.
So, what’s wrong with Peter’s proof?
9. Give an example of three sets W, X, Y such that W ∈ X and X ∈ Y but W ∈
/ Y . (Don’t
mix up the symbol ∈ with the symbol ⊆.)
10. Consider all the five-element subsets of {1, 2, 3, . . . , n}. It is known that one quarter of
these subsets contain the element 7. What is the value of n?
11. Determine whether each of these functions is a bijection from R to R.
(a) f (x) = −3x + 4
(b) f (x) = 3x2 + 4
(c) f (x) = (x + 1)/(x + 2)
12. Let f : R → R be a function where f (x) = x2 . For any subset A of R, we use f (A) to
denote the set {f (x) | x ∈ A}. Determine f (A) for the following subsets A taken from the
domain R.
(a) A = {2, −3}
(b) A = (−3, 3)
(c) A = (−3, 2]
(d) A = (−4, −3] ∪ [5, 6]
13. Define g : Z → Z, where g(n) = bn/2c. Is g a surjection? Is g a bijection?
