0
$\begingroup$

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

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

$\endgroup$
  • 1
    $\begingroup$ @Lovsovs That's not onto. $\endgroup$ – Patrick Stevens Apr 23 '17 at 8:19
6
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

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

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

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

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.