MATHEMATICS 3 question

Question

Prove that there is a mapping from a set to itself that is one-to-one but not onto iff there is a mapping from the set to itself that is onto but not one-to-one. [Hint: You need to distinguish between the codomain and range of such a mapping.]

Answer 1

First of all, for a finite set S, a map from S to itself is one-to-one (aka injective) if and only if it is onto (aka surjective). Therefore either there is a map from S to itself that is one-to-one but not onto, or it is onto but not one-to-one, it is equivalent to the infinitude of the set S. The first condition that there is a map from S to itself that is one-to-one but not onto certainly implies the infinitude of S. To see that such a map always exists for an infinite set S, remember that any infinite set must contain a countable (and infinite) proper subset T={t_1,t_2,...}, which is a sequence of (distinct) elements t_i of S. To define a map f: S--> S that is one-to-one but not onto, we simply define f(x)=x for any x not in T, and for any t_i in T, define f(t_i)=t_{2i}. Obviously f is one-to-one, but it misses all the t_i in T with i being odd. Therefore f is not onto.

On the other hand, Define f(x)=x for x not in T, and for t_i in T, define f(t_i)=t_i if i is odd, and f(t_{2j})=t_j for i=2j even. Obviously f is not one-to-one as f(t_1)=f(t_2)=t_1. But it is onto, as t_i=f(t_i) for i odd, and t_{2j}=f(t_{4j}) for i=2j even.