 #### 联系方式

• QQ：99515681
• 邮箱：99515681@qq.com
• 工作时间：8:00-20:00
• 微信：codinghelp #### 您当前位置：首页 >> Java编程Java编程

###### 日期：2021-12-05 05:06

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.