$f: \mathbb N \to \mathbb N $ be defined as $f(n) = \begin{cases} \dfrac{n}{2}, & \text{if $n$ is even} \\ \dfrac{n+1}{2}, & \text{if $n$ is odd} \end{cases}$

How do I prove that the function is surjective but not injective?


It's not injective because $f(1)=f(2)$ but I doubt that it's a valid proof.

I am new to proof writing in functions therefore I am unable to frame the language for surjective proof. I know that for a surjective function range of function = co domain of function.

  • $\begingroup$ You are right! it is true if $f(1)=f(2)$ then it is not injective. $\endgroup$ – GhD Jan 10 '18 at 17:00
  • $\begingroup$ @GhD Is that the only way to write the proof? $\endgroup$ – Abcd Jan 10 '18 at 17:02
  • $\begingroup$ No, but it is enough to prove that it is not injective. $\endgroup$ – GhD Jan 10 '18 at 20:12

For each $n \in \Bbb N,$

$$f (2n)=n $$

so, it is surjective.

  • $\begingroup$ I don't know what can be explained. He literally proves surjection by definition. $\endgroup$ – user370967 Jan 10 '18 at 17:11

When someone says "all cats are white", if you want to prove that his/her statement is false, all you need to do is to find a cat that is not white. I am telling this because you said you are new to proof writing but in some cases, proofs are really that straight-forward. So your proof is valid for injectivity because all you needed was an example contradicting the assumption of the fuction being injective, and you found one as $f(1) = f(2)$.

And for $f: \mathbb{N} \to \mathbb{N}$ to be surjection, range of $f$ must be $\mathbb{N}$ and even when the function is defined as $f(n) = \frac{n}{2}$ where $n$ is even, this function is surjective because if $n$ is even, then we can write $n = 2k$ where $k \in \mathbb{N}$. Then the function becomes $f(2k) = k$, $k \in \mathbb{N}$. Notice that RHS of this equation is range of $f$ and we have $k \in \mathbb{N}$. So range is $\mathbb{N}$. So $f$ is surjective.


That's basically enough for a proof. If you want to make it more explicit, you can use three sentences:

If function is injective, then $f(x) = f(y)$ means $x = y$. But $f(2) = f(1)$, even though $2 \neq 1$. So the function cannot be injective.

The nice thing about this proof is that each sentence acts like a fact or a deduction. We introduce the definition of injective functions in the first sentence. We introduce our true sentence about the function that we just found out (you can put any calculation here). And in the final sentence, we use those two facts and deduce a property of $f$.

  • 1
    $\begingroup$ That's only one half of what needs to be proved wrt the given question statement, and the asker was spot on about why it is not injective. You haven't though, addressed surjectivity. $\endgroup$ – Namaste Jan 10 '18 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.