The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+9 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.
asked in Set Theory & Algebra by Veteran (99.8k points) | 320 views

1 Answer

+14 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.
answered by Loyal (9k points)
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. 

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

37,980 questions
45,481 answers
48,454 users