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.

+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.

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.

+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.

I think it is simply f : S--->S , is'nt it.

+3

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

0

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.

52,345 questions

60,513 answers

201,931 comments

95,362 users