Exercises 2

1. Which of the following are one-one functions, onto functions or one-one correspondences ?
   (a)  f : R R with f (x) = x²
   (b)  f : R R with f (x) = x³
   (c)  f : Z Z with f (x) = x³
   (d)  f : N N with f (x) = x²
   (e)  f : Z Z with f (x) = x + 7
   (f)  f : N N with f (x) = x + 7
   (g)  f : R R with f (x) = 9x - x³
   (h)  f : R R with f (x) = sin(x)

   Solution to question 1

2. Let f : X Y 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 | a A } and f ^-1[B] = {a X | f (a) B }.
   (a) Prove that f [ A B] 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.

   Solution to question 2

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.

   Solution to question 3

4. Define a map from N N to N by mapping (m , n) to 2^m3ⁿ.
   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.

   Solution to question 4

5. Prove that the set {1, 2, 3, ... , n} has 2ⁿ 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.

   Solution to question 5

6. Let f(m , n) be the function
   (m² + 2mn + n² - 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.

   Solution to question 6