stronger result that p is increasing, that is, if x, y ∈ Z and x < y, then p(x) < p(y). This follows from the fact the function of real variable f(x) = x3 + 1 is increasing. Finally we show that p is not surjective. If n ! 2, p(n) ! p(2) = 9. On the other hand if n " 1, p(n) " p(1) = 2. Therefore p(n) )= 3 for any integer n. (e) X is a nonempty set, Y = P(X) (the set of all subsets of X), h(x) = {x}. Solution: The function h : X → P(X), x '→ {x} is injective because if {x} = h(x) = h(y) = {y}, then x = y. However h is not surjective because the empty set ∅ ∈ P(X) does not satisfy h(x) = {x} = ∅ for any x ∈ X . *3. Given finite sets A and B, let E be a subset of A× B. For a ∈ A, let E(a) = { b ∈ B | (a, b) ∈ E } and for b ∈ B, let E∨(b) = { a ∈ A | (a, b) ∈ E }. Prove that ∑ a∈A |E(a)| = ∑ b∈B |E∨(b)|. Solution: Find the cardinality |E|. For each a ∈ A there are |E(a)| pairs (a, y) ∈ E and so |E| = ∑ a∈A |E(a)|. Similarly, for each b ∈ B there are |E∨(b)| pairs (x, b) ∈ E and therefore |E| = ∑ b∈B |E∨(b)|. Equating these two expressions for |E| gives the result.