How to formalize the fact that $f(i)=\lceil i/2\rceil$ is surjective but not one-to-one from $\Bbb N$ to itself?

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.

• Welcome to MSE. Please use MathJax. – José Carlos Santos May 15 '18 at 16:35
• "So in the codomain, there will be some elements that have no pre-image for this countably infinite set." Why do you say that? You just seemed to give an argument that it would. Anyway for any $n$ then both $2n$ and $2n+1$ will map to $n$. So $f$ is onto. – fleablood May 15 '18 at 16:47
• sir , since , cardinality of both sets are same and every 2 elements of domain are mapped to one element of codomain . so intuitively , it looks that some elements of codomain will not have any pre-image. please correct me – ankit1729 May 15 '18 at 16:51
• You just should that $1,2,3$ and $\frac n2$ (assuming $n$ is even) all have pre-images. What elements don't have pre-images? I honestly don't understand why you said that. – fleablood May 15 '18 at 16:51
• Are you thinking because you will run out of elements? But the set is infinite. You will never run out. So it's perfectly fine to have 2, 3 or even an infinite number of elements all map to the same element and still be onto. In fact that is exactly what you are proving. It is possible to be surjective and not 1-1. – fleablood May 15 '18 at 16:54

2 Answers

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

Maybe I'm missing something. For every n in codomain, 2n and 2n-1 are in preimage, so the mapping is onto but not 1-1

• sir , it may or may not be one-one – ankit1729 May 15 '18 at 17:11