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?

Answer

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

From there, we can use any of the bijections NZ 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:NZ (where we take N to include 0):

s(n)=(1)nn+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=pa11pa22Z+, 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

Leave a Comment