291 views
If the set $S$ has a finite number of elements, prove that if $f$ maps $S$ onto $S$, then $f$ is one-to-one.

Let set $S=\{1,2,3,4\}.$
Now see the mapping from $S$ to $S.$
For $f$ to be onto every element of codomain must be mapped by every element in domain.
Since, cardinality is same for both domain and codomain, we can not have mapping like $f(1)=1, f(2)=1$ because if it happened then at least one element remain unmapped in codomain, which result in $f$ being not onto but it is given that $f$ is onto. So every element in codomain has exactly one element in domain. Thus $f$ must be an one-to-one function.

NOTE: If $S$ is infinite then this result may not be true.
edited by
0
Nice explanation...
+1
What is the meaning of this line " if f maps S onto S "?    Is it simply f : S--->S  ? or f : S--->S  is ONTO?

I think it is simply f : S--->S  , is'nt it.
+2
No the second one you mentioned that mapping from function S to s is onto!
0

Thanks, buddy.

+2

I am not sure but-

If S is infinite then -
For infinite sets, Cardinality is defined in terms of comparision of sets.
Two sets A and B are equipotent(having the same cardinality ), if there exists a bijective function$f: A \rightarrow B$.

Now for a countably infinite set. If it is given that f: S $\rightarrow$ S is a surjective(onto) function. And we know that they are equipotent. So they must be one to one.
Because it's given that f is onto. I can write function f as a composition of 2 counting functions  $g: S \rightarrow N$ and $h: N \rightarrow S$ where N is set of natural numbers, such that f =hog(x)..
Note that writing f as a composition of g and h won't change this function.

So, by the definition of countably infinite sets- g and h both are bijective functions so their composition is also bijective.

EDIT -
I wrote function f as a composition of 2 functions g:S→N and h:N→S.
This is fine..g and h are just counting functions so they are bijective.
But if f is onto but not one to one then one of these functions g and h must not be one to one..

So we can't write every f as a composition of these 2 functions..Only those f that are bijections can be written like this.

So the conclusion is -
Above theorem is not valid for infinite sets whether they are countable or uncountable.
Discussion