A bijection from the naturals to the integers

Statement

Define $g : \mathbb{N} \to \mathbb{Z}$ by $g(n) = \begin{cases} \dfrac{n+1}{2} & \text{if } n \text{ is odd},\\[4pt] -\dfrac{n}{2} & \text{if } n \text{ is even}.\end{cases}$ Prove that $g$ is a bijection.

Solution

The first values are $g(0)=0,\ g(1)=1,\ g(2)=-1,\ g(3)=2,\ g(4)=-2,\dots$: the function lists all integers in order.

Surjectivity. Let $z \in \mathbb{Z}$.

• If $z > 0$, take $n = 2z - 1$ (odd): $g(n) = \frac{(2z-1)+1}{2} = z$.
• If $z \le 0$, take $n = -2z$ (even, $\ge 0$): $g(n) = -\frac{-2z}{2} = z$. In every case $z$ has a preimage, so $g$ is surjective.

Injectivity. The values on odd inputs are all positive ($\ge 1$), those on even inputs are all $\le 0$: so two numbers of different parity have different images. On the odd inputs $n \mapsto \frac{n+1}{2}$ is strictly increasing, hence injective; likewise on the even inputs with $n \mapsto -\frac{n}{2}$. Therefore $g$ is injective.

Being injective and surjective, $g$ is a bijection. $\blacksquare$