# What is an example of function $f: \Bbb{N} \to \Bbb{Z}$ that is a bijection?

Could you give me an example of function $f \colon \mathbb N \to \mathbb Z$ that is both one-to-one and onto? Does this work: $f(n) := n \times (-1)^n$?

N starts with zero.

• Does $\mathbb{N}$ start with one or zero? – hardmath Oct 9 '14 at 17:11
• no, that is not onto: there's no $n$ such that $f(n)=1$ – Exodd Oct 9 '14 at 17:12
• It starts with zero – Fan Oct 9 '14 at 17:12
• – GEdgar Feb 8 '15 at 17:34

## 8 Answers

First note that $\Bbb{Z}$ contains all negative and positive integers. As such, we can think of $\Bbb{Z}$ as (more or less) two pieces. Next, we know that every natural number is either odd or even (or zero for some people) so again we can think of $\Bbb{N}$ as being in two pieces. lastly, let's try to make a map that takes advantage of the "two pieces" observation . That is, let's make a function from evens/odds to positives/negatives. Let $f: \Bbb{N} \to \Bbb{Z}$ where

$$f(n) = \begin{cases} \frac{n}{2} & n\text{ is even} \\ -\frac{n + 1}{2} & \text{else} \end{cases}$$

This map is a bijection, although I will leave the proof of that up to you.

$$f(n) = n\text{th number in the sequence }0, 1, -1, 2, -2, \ldots$$

$$f\colon \Bbb N \to \Bbb Z, \qquad f(n)= \begin{cases} \quad\dfrac n2\qquad \text{if n is even}\\ -\dfrac {n+1}{2}\quad \text{if n is odd} \end{cases}$$

• I believe that this function is not one-to-one. Notice that both f(0) and f(1) evaluate to 0. – Bill Province Oct 9 '14 at 17:32
• In $\Bbb N$ where do you get $0$?? – user152715 Oct 9 '14 at 17:39
• @ Bill Province There is no universal agreement about whether to include zero in the set of natural numbers. Some authors begin the natural numbers with $0$, corresponding to the non-negative integers ${0, 1, 2, 3, ...}$, whereas others start with $1$, corresponding to the positive integers ${1, 2, 3, ...}$. I have rule out $0$ in $\Bbb N$. – user152715 Oct 9 '14 at 17:45
• Agreed that there is no universal agreement on inclusion of 0 in N. However, the problem statement clarifies the notion, and includes N starting with 0. – Bill Province Oct 9 '14 at 17:52
• Oh ok. I missed that line. Thank you. At first I have also posted with $(n+1)$ then changed it.. – user152715 Oct 9 '14 at 18:15

Here is a slight modification of OP's suggestion: The function $f(n):=\sum_{k=0}^n (-1)^k k$ is a bijection $f:\mathbb{N}_0\to \mathbb{Z}$.

$$f(n) = \left\{\begin{array}{cc} \frac{n}{2} & n \textrm{ is even,}\\ \frac{-(n+1)}{2} & n \textrm{ is odd.} \end{array} \right.$$

Hence, $$f(0) = 0,$$ $$f(1) = \frac{-(1+1)}{2} = -1,$$ $$f(2) = \frac{2}{2} = 1,$$ $$f(3) = \frac{-(3+1)}{2} = -2 \cdots$$

Here are lots of answers . . . well not really, they are actually all in effect the same. In each of them we take $f(0)=0$ and I give instructions for the rest.

1. $f(n)=k$ if $n$ is the $k$th prime, $f(n)=-k$ if $n$ is the $k$th non-prime.
2. $f(n)=k$ if $n$ is the $k$th (non-zero) square, $f(n)=-k$ if $n$ is the $k$th non-square.
3. $f(n)=k$ if $n$ is the $k$th power of $2$, $f(n)=-k$ if $n$ is the $k$th non-power of $2$.

. . . and so on . . . not forgetting

1. $f(n)=k$ if $n$ is the $k$th even number, $f(n)=-k$ if $n$ is the $k$th odd number,

which is actually the example already given by many people.

$$f(n)=\frac{1-(2n+1)\cos n\pi}4$$

$$f(n)=(-1)^n \left \lceil \frac{n}{2} \right \rceil$$

where $\lceil x \rceil$ rounds up a real value (see ceiling function).