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

- Which of the following are one-one functions, onto functions or one-one correspondences ?

(a)*f*:**R**→**R**with*f*(*x*) =*x*^{2}

(b)*f*:**R**→**R**with*f*(*x*) =*x*^{3}

(c)*f*:**Z**→**Z**with*f*(*x*) =*x*^{3}

(d)*f*:**N**→**N**with*f*(*x*) =*x*^{2}

(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*) = 9*x*-*x*^{3}

(h)*f*:**R**→**R**with*f*(*x*) = sin(*x*) - 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. - 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. - Define a map from
**N × N**to**N**by mapping (*m*,*n*) to 2^{m}3^{n}.

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. - Prove that the set {1, 2, 3, ... ,
*n*} has 2^{n}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. - Let
*f*(*m*,*n*) be the function

(*m*^{2}+ 2*mn*+*n*^{2}- 3*m*-*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.

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