MTH 231 Quiz 2
Name_________________________________________
Instructions: Please present complete solutions to each of these problems. You may need to attach additional paper to
adequately show your work and explain your reasoning.
1. Define the following infinite collection of subsets of the positive integers:
?1 = {?|? ∈ ℤ
+
and 0 ≤ ? < 10}, ?2 = {?|? ∈ ℤ
+ and 10 ≤ ? < 20}, ?3 = {?|? ∈ ℤ
+ and 20 ≤ ? < 30}, …
Let R be the “in the same subset” relation. ? ? ? if and only if ∃? such that ? ∈ ?? and ? ∈ ??.
a. Explain why each of the following statements are true.
17 R XXXXXXXXXXR 29
. Prove that R is an equivalence relation on the set of positive integers.
c. Use a particular counterexample to explain why R fails to be an equivalence relation on the set of positive
integers if the definition of the subsets is adjusted as follows:
?1 = {?|? ∈ ℤ
+
and 0 < ? < 10}, ?2 = {?|? ∈ ℤ
+ and 10 < ? < 20}, ?3 = {?|? ∈ ℤ
+ and 20 < ? < 30}, …
Use a particular counterexample to explain why R fails to be an equivalence relation is the definition of the
subsets is adjusted as follows:
?1 = {?|? ∈ ℤ
+
and 0 ≤ ? ≤ 10}, ?2 = {?|? ∈ ℤ
+ and 10 ≤ ? ≤ 20}, ?3 = {?|? ∈ ℤ
+ and 20 ≤ ? ≤ 30}, …
2. Recall that a binary tree is complete if every vertex (other than the leaves) has 2 offspring. Consider a complete
inary tree of height n in which all of the leaves appear at the same level (that is, all of the leaves appear in level n).
a. How many leaves would there be in such a binary tree? Explain your reasoning.
. How many vertices (including the leaves) would there be in such a binary tree? Explain your reasoning.
c. How many edges would there by in such a binary tree? Explain your reasoning.