Self Doubt. Related to https://gateoverflow.in/94634/gate1988-13ii#c216658.

Question

1. If the set $S$ is countably infinite, prove or disprove that if $f$ maps $S$ onto $S$ (i.e $f:S \rightarrow S$ is a surjective function), then $f$ is one-to-one.

Comments

some discussion https://gateoverflow.in/216802/set-theory

---

@Saumya29-You cannot have a surjective function $f: A \rightarrow B$ such that $|A| \leq |B|$

it is possible only when $|B| \leq |A|$

---

Ohh Yeah. It was a typo. Thanks, Ayush.

Answer 1

this statement always doesn't hold.It depends on what the function f is.

Suppose the mapping is from N(natural number set,countably infinite) -> N.And  f(i)=  $\left \lceil \frac{i}{2} \right \rceil$.it is onto function but not one-one.

Comments

@ankit @kushagra.. Above example looks perfectly fine.

What i did in my comment on that que is ,
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 that 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 composition of these 2 functions..Only those f that are bijections can be written like this.

---

could u please prove that all the elements of co-domain will be covered according to function f(i)=  ⌈i/2⌉..since , 1 and 2 will be mapped to 1..3 and 4 will be mapped to 2...5 and 6 will be mapped to 3....similarly, n-1,n will be mapped to n/2...so in codomain , some elements will be existed for which there will be no pre-image...please correct me if I m wrong..

---

Take any element x in codomain the respective preimage will be 2x in the domain.