If the set $S$ is countably infinite, prove or disprove that if $f$ maps $S$ onto $S$ (i.e. $f\colon S\to S$ is a surjective function), then $f$ is one-to-one mapping.
Please give a formal mathematical proof for this statement.
I have a counter-example: Suppose the mapping is from $\Bbb N$ (the natural numbers, a countably infinite set) to $\Bbb N$. And $f(i) = \lceil i/2\rceil$. It is onto function but not one-one.
But I am not getting that how this mapping is onto. Intuitively, 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$ and $n$ will be mapped to $n/2$. So in the codomain, there will be some elements that have no pre-image for this countably infinite set. So, please correct me where I am wrong.
To prove that a function $f\colon A\to B$ is surjective, you need to be able to prove that given $b\in B$, there is some $a\in A$ such that $f(a)=b$.
In your case, $A=B=\Bbb N$, and $f(x)=\lceil \frac x2\rceil$.
So you need to prove that given any $m\in\Bbb N$, there is some $n\in\Bbb N$ such that $\lceil\frac n2\rceil=m$. Even though this $n$ is not unique, I am sure that you can come up with a way to find such $n$, from a given $m$.