GATE CSE 1988 | Question: 13ii

Question

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

Comments

Refer link for proof:

https://math.stackexchange.com/questions/989043/rigorous-proof-that-surjectivity-implies-injectivity-for-finite-sets 

---

Note1 : This  is true only because the set is finite ( not for infinite set ). 

Note2 : This can be proof using proof of contradiction by considering " f is not one-one function" 

Proof :

Let $f: S \to S$ and $|S| = n$. For any valid function:

$$|f(S)| \le |S| = n$$

If $f$ is onto, then by definition the image equals the codomain ($f(S) = S$), which gives:

$$|f(S)| = n$$

Now, if $f$ were not injective, a collision would occur. Any collision reduces the total number of unique outputs below the number of inputs, forcing:

$$|f(S)| < n$$

This directly contradicts the fact that $|f(S)| = n$. Therefore, $f$ must be injective.

 

Answer 1

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.

Comments

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.

---

For infinite set(given f is onto) :

f: Z→ Z

f(x)=  $\left\{\begin{matrix} \frac{x}{2} &, x =even \\ 2x-1&, x= odd \end{matrix}\right.$

Here f is onto but not one-one.

f(1)= 1, f(2)=1. So not one-one but f is onto.

Answer 2

proof by contradiction.