The Gateway to Computer Science Excellence
+13 votes
If the set $S$ has a finite number of elements, prove that if $f$ maps $S$ onto $S$, then $f$ is one-to-one.
in Set Theory & Algebra by | 728 views

1 Answer

+21 votes
Best answer
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
Nice explanation...
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.
No the second one you mentioned that mapping from function S to s is onto!

Thanks, buddy.


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.

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. 


Given f is onto. To prove f is one-to-one under the given condition that f maps S to S.

We can imagine it like there are n boxes(range) and n balls(domain) and each box has to be filled with at least one ball [Similar to onto property]

In the 1st round we put a ball in each of the boxes and if we are left with any extra ball then we place that in the 2nd round.

After finishing the 1st round we know that to fill up all the boxes we have needed n balls. 

Are we left with extra balls? No. 

Also we can observe that each ball has been kept in some different box that made it possible to fill all the n boxes -->Similar to one-to-one property.

Had we been left with extra balls then we would have put it again in one of the n boxes which would mean one box getting more than 1 balls --> not an one-to-one property. 


^ basically an application of pigeonhole principle. If domain had $n + 1$ elements and the codomain had $n$, then atleast two domain elements would map to the same codomain element.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,513 answers
95,362 users