# Produce an explicit bijection between rationals and naturals?

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?

We will first find a bijection $$h+:Z+→Q+h_{+}:\mathbb Z^+\to \mathbb Q^+$$. From there, we easily get a bijection $$h:Z→Qh:\mathbb Z\to \mathbb Q$$ by defining: $$h(n)={h+(n)n>00n=0−h+(−n)n<0h(n)=\begin{cases}h_{+}(n)&n>0\\ 0&n=0\\ -h_{+}(-n)&n<0 \end{cases}$$

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

Now, every positive integer can be written uniquely as $$pa11pa22⋯p_1^{a_1}p_2^{a_2}\cdots$$, where the $$p1=2,p2=3,p3=5,…p_1=2,p_2=3,p_3=5,\dots$$ is the sequence of all primes, and the $$aia_i$$ are non-negative integers, and are non-zero for only finitely many $$ii$$s.

Similarly, every positive rational number can be written uniquely as $$pb11pb22⋯p_1^{b_1}p_2^{b_2}\cdots$$ where the $$bib_i$$ are integers and only finitely many of the $$bib_i$$ are non-zero.

So define $$s:N→Zs:\mathbb N\to\mathbb Z$$ (where we take $$N\mathbb N$$ to include $$00$$):

$$s(n)=(−1)n⌊n+12⌋s(n)= (-1)^n\left\lfloor\frac{n+1}{2}\right\rfloor$$

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

Then for any $$n=pa11pa22⋯∈Z+n=p_1^{a_1}p_2^{a_2}\cdots\in\mathbb Z^+$$, define $$h+(n)=ps(a1)1ps(a2)2⋯h_{+}(n)=p_1^{s(a_1)}p_2^{s(a_2)}\cdots$$

This then defines our bijection $$h+:Z+→Q+h_{+}:\mathbb Z^+\to \mathbb Q^{+}$$.

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

We again assume $$0\in\mathbb N.0\in\mathbb N.$$

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

We will also use that if $$q\neq 1q\neq 1$$ is a positive rational number, then $$qq$$ 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}}}\left[a_0,a_1,\dots,a_k\right]=a_0+\cfrac1{a_1+\cfrac{1}{\ddots +\cfrac{1}{a_k}}}$$ where $$a_0a_0$$ is a non-negative integer, the other $$a_ia_i$$ are positive integers, and $$a_k>1.a_k>1.$$

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

\begin{align} &g_+(\emptyset)=1\\ &g_+(\{n\})=n+2\\ &g_+\left(\left\{b_00 \end{align}\begin{align} &g_+(\emptyset)=1\\ &g_+(\{n\})=n+2\\ &g_+\left(\left\{b_00 \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 Qb:\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}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.\mathbb N\to\mathbb Z.$$ You can use the function $$ss$$ from the previous section. Then $$b\circ sb\circ s$$ is a bijection.

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

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

$$g_+g_+$$ is nice because it can be extended to $$\mathcal P(\mathbb N)\to\mathbb R^+\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.