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).
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.