prove that the function is surjective but not injective.

Question

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

Attempt:

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.

Answer 1

For each $n \in \Bbb N,$

$$f (2n)=n $$

so, it is surjective.

Answer 2

When someone says "all cats are white", if you want to prove that this 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.

Answer 3

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