# Function that is onto, but not one-to-one.

$f:\mathbb{Z}\rightarrow \mathbb{Z}$

Would a piece wise function work here? What other functions would work too?

• @Lovsovs That's not onto. – Patrick Stevens Apr 23 '17 at 8:19

$$f(n) = \begin{cases} n & \text{ if } n \text{ is odd} \\ \frac{n}{2} & \text{ if } n \text{ is even} \end{cases}$$

Take $n\to \lfloor n^{1/3}\rfloor$ for example.

• Very nice example! – Taladris Apr 23 '17 at 8:25
• Thanks, we'll see how the OP will like to write the proof (several styles !) – Duchamp Gérard H. E. Apr 23 '17 at 8:28

Going at this from a "I know a bit about ordinals" perspective (which you don't need! it's just the inspiration for this answer):

There's a bijection $g: \mathbb{N}_{\geq 1} \to \mathbb{Z}$ given by sending $a$ to $\frac{a}{2}$ if $a$ is even, and $-\frac{a-1}{2}$ if $a$ is odd. (This is where the ordinals came in: I well-ordered $\mathbb{Z}$.) So it's enough to find a surjective non-injective function $\mathbb{N}_{\geq 1} \to \mathbb{N}_{\geq 1}$.

That's easy: send $1 \mapsto 1$ (the simplest thing we could do!), and then $n \mapsto n-1$ for $n \geq 2$ (which is the first thing that sprang to mind when I tried to find a non-injective function).

• I changed $\mathbb{N}^{\geq 1}$ to $\mathbb{N}_{\geq 1}$. I believe the latter is more standard notation. – wythagoras Apr 23 '17 at 8:34
• @wythagoras Thanks; I don't think I've ever seen a standard notation for this so I just used something unambiguous. – Patrick Stevens Apr 23 '17 at 8:37