I remember my professor in college challenging me with this question, which I failed to answer satisfactorily: I know there exists a bijection between the rational numbers and the natural numbers, but can anyone produce an explicit formula for such a bijection?

**Answer**

We will first find a bijection h+:Z+→Q+. From there, we easily get a bijection h:Z→Q by defining: h(n)={h+(n)n>00n=0−h+(−n)n<0

From there, we can use any of the bijections N→Z to get our bijection between N and Q. (We'll need a specific such bijection below, s.)

Now, every positive integer can be written uniquely as pa11pa22⋯, where the p1=2,p2=3,p3=5,… is the sequence of all primes, and the ai are non-negative integers, and are non-zero for only finitely many is.

Similarly, every positive rational number can be written uniquely as pb11pb22⋯ where the bi are integers and only finitely many of the bi are non-zero.

So define s:N→Z (where we take N to include 0):

s(n)=(−1)n⌊n+12⌋

The sequence s(0),s(1),s(2),s(3),… would be 0,−1,1,−2,2…, and this is a bijection from N to Z. The only properties we really need for s is that s is a bijection and s(0)=0.

Then for any n=pa11pa22⋯∈Z+, define h+(n)=ps(a1)1ps(a2)2⋯

This then defines our bijection h+:Z+→Q+.

A potientially interesting feature of h+ is that it is multiplicative - that is, if gcd then h_{+}(mn)=h_+(m)h_{+}(n).

**Another answer.**

We again assume 0\in\mathbb N.

We will need an explicit bijection \phi:\mathbb N\to\mathcal P_{\text{Fin}}(\mathbb N), where \mathcal P_{\text{Fin}}(\mathbb N) is the set of all finite subsets of \mathbb N.

We will also use that if q\neq 1 is a positive rational number, then q can be written uniquely as a continued fraction:

\left[a_0,a_1,\dots,a_k\right]=a_0+\cfrac1{a_1+\cfrac{1}{\ddots +\cfrac{1}{a_k}}} where a_0 is a non-negative integer, the other a_i are positive integers, and a_k>1.

We define g_+:\mathcal P_{\text{Fin}}(\mathbb N)\to\mathbb Q^{+} as:

\begin{align}

&g_+(\emptyset)=1\\

&g_+(\{n\})=n+2\\

&g_+\left(\left\{b_0<b_1<\cdots<b_k\right\}\right)=\left[b_0,b_1-b_0,\dots,b_{k-1}-b_{k-2},b_{k}-b_{k-1}+1\right],\quad k>0

\end{align}

The uniqueness of the continued fractions ensures this is a bijection. We had to do some a slight hack to deal with the problem of the empty set.

Then we define b:\mathbb Z\to \mathbb Q similar to before:

b(m)=\begin{cases}

0&m=0\\

g_+(\phi(m))&m>0\\

-g_+(\phi(-m))&m<0

\end{cases}

And then compose with any bijection \mathbb N\to\mathbb Z. You can use the function s from the previous section. Then b\circ s is a bijection.

This leaves \phi, but every natural number n can be written uniquely in binary, as n=\sum_{a\in A_n} 2^{a} for some finite set A_n\subseteq \mathbb N. Then we can take \phi(n)=A_n.

This means that if n\in\mathbb N then b(2^n)=n+2 and b(0)=1. Also, b(1+2^n)=g_+(\{0,n\})=\frac{1}{n+1}.

g_+ is nice because it can be extended to \mathcal P(\mathbb N)\to\mathbb R^+ to show a bijection between these two sets, because every irrational number has a unique infinite continued fraction.

**Attribution***Source : Link , Question Author : Alex Basson , Answer Author : Thomas Andrews*