Show that a function from a finite set S to itself is onetoo

Show that a function from a finite set S to itself is one-to-one if and only if it is onto. Is this true when S is infinite ?

Solution

The definition of onto is :

Given a function g:A->B, for all b that are elements of B, there exists an aA such that g(a)=b.

Let, function f is not onto, thus there exists b that is an element of S, such that there does not exist any aS such that f(a)=b.

Thus, the image of f is at most one element smaller than that of the domain (remember, b isn\'t in the image).

But if this is true, then because f is finite and a function, all elements in S have to map to one and only one element in S/{b}. However, all the unique pairs can be exhausted, i.e. f(a1)=b1, f(a2)=b2..., f(an)=bn, until we eventually arrive at a situation where one element in the domain still needs to be paired and the only element left in S is b.

However, f(a) doesn\'t equal b as we have shown for any aS, thus this is a contradiction. Hence, a function from a finite set S to itself is one-to-one if and only if it is onto.

Also, it is not necessarily true for infinite sets because the norm of an infinite set can still equal the norm of that same set minus 1 or some other finite (and in some cases infinite) number of elements.