PRACTICE FINAL SOLUTIONS - MA109 Problem 1 (10 pts): A (2 pts): Write down the definition of a surjective function from the set X to the set Y . A function f : X → Y is surjective if for every y ∈ Y , there is x ∈ X with f(x) = y. B (2 pts): Given n, k ∈ N ∪ {0} with n ≥ k, write down the definition of (nk). The number ( n k ) is the cardinality of the set Pk([n]), the set of k-element subsets of [n]. C (2 pts): Given sets X and Y , write down the definition of the set YX. The set Y X is the set of functions from X to Y . D (2 pts): Write down the definition of a finite set. A set X is finite if for some n ∈ N ∪ {0}, there is a bijection f : [n]→ X. E (2 pts): Write down the definition of the power set of the set X. The power set of a set X is the set of all subsets of X. Problem 2 (10 pts): Prove by induction that for every n ∈ N, if qn, rn ∈ Z are the unique numbers with 0 ≤ rn < 3 and 5n = 3qn + rn, we have rn = 2 if n = 3k + 1 for some k ∈ Z, 1 if n = 3k + 2 for some k ∈ Z, 0 if n = 3k for some k ∈ Z. Proof : Let P (n) be the following formula: if qn, rn ∈ Z are such that 5n = 3qn + rn and with 0 ≤ rn < 3, then rn is given as above. Base case: P (1) is the statement “if q1 and r1 are the integers satisfying 5 = 3q1+r1 and 0 ≤ r < 3, then r1 = 2.” Since 5 = 3 · 1 + 2, we see that q1 = 1 and r1 = 2, and P (1) holds. Inductive step: Let m ∈ N, and assume P (m) is true. Towards showing that P (m+ 1) holds, there are three cases to consider. Case 1 - If m + 1 = 3k + 1 for some integer k, then m = 3k. As P (m) is true, we must have rm = 0, so that 5m = 3qm. Then we have 5(m+ 1) = 5m+ 5 = (3qm) + 5 = 3(qm + 1) + 2. By the uniqueness part of the division theorem, we must have qm+1 = qm + 1 and rm+1 = 2 as desired. Case 2 - If m + 1 = 3k + 2 for some integer k, then m = 3k + 1. As P (m) is true, we must have rm = 2, so that 5m = 3qm + 2. Then we have 5(m+ 1) = 5m+ 5 = (3qm + 2) + 5 = 3(qm + 2) + 1. By the uniqueness part of the division theorem, we must have qm+1 = qm + 2 and rm+1 = 1 as desired. Case 3 - If m + 1 = 3k for some integer k, then m = 3(k − 1) + 2. As P (m) is true, we must have rm = 1, so that 5m = 3qm + 1. Then we have 5(m+ 1) = 5m+ 5 = (3qm + 1) + 5 = 3(qm + 2). By the uniqueness part of the division theorem, we must have qm+1 = qm + 2 and rm = 0 as desired. As the desired result holds in all three cases, we see that P (m+ 1) is true. By induction, it follows that P (n) is true for every n ∈ N. 1 2 PRACTICE FINAL SOLUTIONS - MA109 Problem 3 (10 pts): Fix q ∈ N. Given m,n ∈ N, we say that a function f : [m] → [n] is q-spaced if for any i 6= j ∈ [m], we have |f(i)− f(j)| ≥ q. Prove that if m,n ∈ N and there is a q-spaced function f : [m]→ [n], then we have n ≥ q(m−1)+1. Proof : We will show that n ≥ q(m−1)+1 by finding a subset of [n] of size q(m−1)+1. Fix f : [m]→ [n] a q-spaced function. In particular, f is injective, so |Im(f)| = m. Write Im(f) = {a1, ..., am} with a1 < a2 < · · · < am. For each i ∈ Z with 2 ≤ i ≤ m, let Ai = {ai − q + 1, ai − q + 2, ..., ai}. For i = 1, simply set A1 = {a1}. Because f is q-spaced, the sets Ai are pairwise disjoint. It follows that |⋃mi=1Ai| = ∑mi=1 |Ai| = 1 + q(m − 1). As ⋃mi=1Am ⊆ [n], we see that n ≥ q(m − 1) + 1 as desired. Problem 4 (10 pts): We say that a set S ⊆ Q is bounded if there are a < b ∈ Q with S ⊆ (a, b). Define X = {S ∈ P(Q) : S is bounded}. Prove that X is uncountable. Proof : First we will find one bounded, countably infinite subset T ⊆ Q. We can take T = {1/n : n ∈ N}; since T ⊆ (0, 1), we see that T is bounded. As T ⊆ Q, we also have P(T ) ⊆ P(Q), and as T is bounded, so is every subset of T . Hence P(T ) ⊆ X. As T is countably infinite, P(T ) is uncountable, implying that X is also uncountable. Problem 5 (10 pts): Let X, Y , and Z be sets. Suppose that f : X → Y and g : Y → Z are injections. Prove that g ◦ f is an injection. Proof : Let x1, x2 ∈ X with x1 6= x2. As f : X → Y is an injection, we have f(x1) 6= f(x2). Then, as g : Y → Z is an injection, we have g(f(x1)) 6= g(f(x2)). Since by definition g ◦ f(x) = g(f(x)) for every x ∈ X, we see that g ◦ f(x1) 6= g ◦ f(x2), and g ◦ f is injective as desired.
欢迎咨询51作业君