KMB, 15/12/99

M1F Foundations of Analysis—Problem Sheet 11

1) For each of the following functions, say whether they are injective, surjective, bijective.

a) f : ℝ → ℝ defined by f(a) = a + 1.

b) f : ℤ → ℝ defined by f(a) = a + 1.

c) f : ℚ → ℝ defined by f(a) = a^{2}.

d) f : ℤ^{2} → ℤ defined by f(a, b) = ab.

e) f : ℚ → ℝ defined by f(a) = (a + \sqrt{2})^{2}.

2) Say f : X → Y is a function, and there exists g : Y → X such that f(g(y)) = y for all y ∈ Y, and g(f(x)) = x for all x ∈ X. Prove that f is a bijection (this is the converse of something we proved in lectures).

3) What’s the coefficient of x^{4} in (1 + x^{2} + x^{−3})^{6}?

4) Show that if 0 ≤ r < n then \binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}.

5)

a) Prove that ℤ^{2} is countable.

b) Prove that the number of equivalence relations on ℤ is uncountable.

c) Prove that the collection of all finite subsets of ℕ is countable.