MT2002 Analysis

 Previous page (Exercises 1) Contents Next page (Exercises 3)

## Exercises 2

1. Which of the following are one-one functions, onto functions or one-one correspondences ?
(a)  f : RR with f (x) = x2
(b)  f : RR with f (x) = x3
(c)  f : ZZ with f (x) = x3
(d)  f : NN with f (x) = x2
(e)  f : ZZ with f (x) = x + 7
(f)  f : NN with f (x) = x + 7
(g)  f : RR with f (x) = 9x - x3
(h)  f : RR with f (x) = sin(x)
2. Let f : XY be a map and let A be a subset of X and let B be a subset of Y.
Define f [A] = {f (a) ∈ Y | aA } and f -1[B] = {aX | f (a) ∈ B }.
(a) Prove that f [ AB] ⊆ f [A] ∩ f [B].
If f is a one-one function prove that these two sets are equal.
(b) Prove that f [ f -1[B]] ⊆ B.
If f is an onto function prove that these two sets are equal.

3. If a finite set A has m elements and a finite set B has n elements, determine how many maps there are from A to B. How many of these maps are one-one ?
Asking how many of these maps are onto is much harder, so you might try looking at the problem for some small values of m , n.
Show that any map from a finite set S to itself which is one-one is also onto, but that this result may fail if S is infinite.

4. Define a map from N × N to N by mapping (m , n) to 2m3n.
Prove that this is a one-one map.
Deduce that N × N may be put into one-one correspondence with a subset of N and hence prove that N × N is countable.
Use a similar method to prove that N × N × ... × N (n times) is countable.

5. Prove that the set {1, 2, 3, ... , n} has 2n subsets (including the empty set φ). Hence show that the set of all finite subsets of N is countable.
Adapt the Cantor diagonalisation argument to show that the set of all subsets of N is not countable.

6. Let f (m , n) be the function
(m2 + 2mn + n2 - 3m - n + 2)/2 = (m + n - 1)(m + n - 2)/2 + n .
Write down the value of f at each point (m , n) of N × N (at least for some small values of m, n) and comment on the result.

SOLUTIONS TO WHOLE SET
 Previous page (Exercises 1) Contents Next page (Exercises 3)

JOC September 2001