Produce an explicit bijection between rationals and naturals?

Solution 1:

We will first find a bijection $h_{+}:\mathbb Z^+\to \mathbb Q^+$. From there, we easily get a bijection $h:\mathbb Z\to \mathbb Q$ by defining: $$h(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 $\mathbb N\to\mathbb Z$ to get our bijection between $\mathbb N$ and $\mathbb Q$. (We'll need a specific such bijection below, $s$.)

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

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

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

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

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

Then for any $n=p_1^{a_1}p_2^{a_2}\cdots\in\mathbb Z^+$, define $$h_{+}(n)=p_1^{s(a_1)}p_2^{s(a_2)}\cdots $$

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

A potientially interesting feature of $h_+$ is that it is multiplicative - that is, if $\gcd(m,n)=1$ 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.

Solution 2:

We will first create a bijection from $\mathbb{N}$ to $\mathbb{Q}^{+}$ and then use this to create a bijection from $\mathbb{N}$ to $\mathbb{Q}$.

Step One: Let us first define Stern's diatomic series. This process formalizes the Stern-Brocot tree mentioned above.

$a_{1} = 1 \\ a_{2k}=a_{k} \\ a_{2k+1}=a_{k}+a_{k+1}$

To get a feel for this series, let us list out the first few terms.

$a_{1}=1 \\ a_{2}=a_{1}=1 \\ a_{3}=a_{1}+a_{2}=1+1=2 \\ a_{4}=a_{2}=1 \\ a_{5}=a_{2}+a_{3}=1+2=3 \\ a_{6}=a_{3}=2 \\ a_{7}=a_{3}+a_{4}=2+1=3 \\ a_{8}=a_{4}=1$

Now to obtain the $n^{th}$ rational number, we define $f: \mathbb{N} \rightarrow \mathbb{Q}^{+}$, by $f(n)= \dfrac{a_{n}}{a_{n+1}}$.

Let us list out the first few terms.

$f(1)= a_{1}/a_{1+1} = 1/1 \\ f(2)= a_{2}/a_{2+1} = 1/2 \\ f(3)= a_{3}/a_{3+1} = 2/1 \\ f(4)= a_{4}/a_{4+1} = 1/3 \\ f(5)= a_{5}/a_{5+1} = 3/2 \\ f(6)= a_{6}/a_{6+1} = 2/3 \\ f(7)= a_{7}/a_{7+1} = 3/1 $

This function enables us to say that the $6^{th}$ rational number is $2/3$. Moreover, this function is a bijection. For proof of this, see Theorem 5.1 here http://faculty.plattsburgh.edu/sam.northshield/08-0412.pdf.

Since $f$ is a bijection this implies that $f^{-1}$ exists. That means given a rational number we can find the corresponding natural number. For example suppose you have a fraction, say it is $1/4$. Can we determine the $n$ such that $f(n)=1/4$? The answer is a resounding yes. Given a positive rational number, $q \in \mathbb{Q}$, the $n$ such that $f(n)=q$ is found by $n=f^{-1}(q)$. This function, $f^{-1}$, is given as follows:

$f^{-1}(1)=1 \\ f^{-1}(q)= 2f^{-1} \bigg(\dfrac{q}{1-q} \bigg) ~ \text{if} ~ q<1 \\ f^{-1}(q) = 2f^{-1}(q-1)+1 ~\text{if}~ q>1$

As an example, we see from above that $f(5)={3/2}$. Let us plug $(3/2)$ into $f^{-1}$ and see if we get 5.

$f^{-1}(3/2)=2f^{-1} \bigg(\dfrac{3/2}{1-(3/2)} \bigg)+1=2f^{-1} \bigg(\dfrac{1}{2} \bigg)+1.$ A quick calculation yields that $f^{-1} \bigg(\dfrac{1}{2} \bigg)=2$ and so we get $f^{-1}(3/2)=2f^{-1} \bigg(\dfrac{1}{2} \bigg)+1=2(2)+1=5$.

Step Two: We showed there exists a bijection between $\mathbb{N}$ and $\mathbb{Q}^{+}$. We now attempt to show there exists an explicit bijection between $\mathbb{N}$ and $\mathbb{Q}$. Using the work done in Step One, it appears easier to first create a bijection between $\mathbb{Z}$ and $\mathbb{Q}$. The reason for doing so is because we have already created a bijection from the positive integers (natural numbers) to the positive rationals. So it only seems natural that by adding in the negative integers, we can map them to the negative rationals and thus obtain a bijection. We do this as follows:

$$ g(z) = \begin{cases} \dfrac{a_{z}}{a_{z+1}}, & \text{if } z>0 \\ \\ - \dfrac{a_{-z}}{a_{-(z-1)}}, & \text{if } z<0 \\ \\ 0, & \text{if } z=0 \end{cases} $$ where the $a_{i}$ term refers to the $i^{th}$ term in Stern's diatomic series.

We already referenced a proof by Northshield showing that $g(z)=\dfrac{a_{z}}{a_{z+1}}$ if $z>0$ is a bijection from $\mathbb{N} \rightarrow \mathbb{Q}^{+}$. Equivalently, we may write this as $g$ is a bijection from $\mathbb{Z}^{+}$ to $\mathbb{Q}^{+}$ for $z>0$. Now, it follows by the symmetry of the problem that $g(z)=- \dfrac{a_{-z}}{a_{-(z-1)}}$ is a bijection from $\mathbb{Z}^{-}$ to $\mathbb{Q}^{-}$ if $z<0$. That is, $g$ is a bijection between the negative integers and the negative rationals. So we have covered all the positive and negative rationals. The only element in the rationals that is not accounted for is the zero element. So we shall have the integer $0$ mapping to the rational number $0$. However, $g$ is a bijection from the integers to the rationals. We wish to find a bijection from the natural numbers to the rationals. So we shall now define the well-known bijection from the natural numbers to the integers.

$$ h(n) = \begin{cases} \dfrac{n}{2}, & \text{if }n\text{ is even} \\ -\dfrac{n-1}{2}, & \text{if }n\text{ is odd} \end{cases} $$

You may check for yourself that $h$ is a bijection. It follows that $g~\circ~ h: \mathbb{N} \rightarrow \mathbb{Q}$ is a bijection since the composition of two bijections is a bijection. Thus, we have an explicit bijection from $\mathbb{N}$ to $\mathbb{Q}$.

However, given a rational number, can we find what this rational number maps to in the set of natural numbers? Although I do not prove it, the answer is yes and is given by the following piece-wise defined function which is an extension of the function defined in Step One. We first define $g^{-1}: \mathbb{Q} \rightarrow \mathbb{Z}$ as

$$ g^{-1}(q) = \begin{cases} 2f^{-1}(q-1)+1, & \text{if } q>1 \\ 1, & \text{if } q=1 \\ 2f^{-1} \bigg(\dfrac{q}{1-q} \bigg), & \text{if } 0<q<1 \\ 0, & \text{if } q=0 \\ -2 \Bigg(f^{-1} \bigg(\dfrac{-q}{1+q}\bigg) \Bigg), & \text{if } -1<q<0 \\ -1, & \text{if } q=-1 \\ -2(f^{-1}(-q-1)+1), & \text{if } q<-1 \end{cases} $$

We now define the function $h^{-1}: \mathbb{Z} \rightarrow \mathbb{N}$ as follows:

$$ h^{-1}(z)= \begin{cases} 2z, & \text{if } z>0 \\ 1, & \text{if } z=0 \\ -2z-1, & \text{if } z<0 \\ \end{cases} $$

Then $h^{-1} \circ g^{-1}: \mathbb{Q} \rightarrow \mathbb{N}$ is the bijection we are looking for.

Solution 3:

Recently I was reading some papers by Don Zagier and found this one most interesting. Here, you can get not only a satisfactory proof of the bijection, but also you will have the notion of the rational number immediately after, or before, a given number, which we don't have in Cantor's proof.

Theorem:

The map $$S(x)=\frac{1}{2\lfloor x\rfloor-x+1}$$ has the property that, among the sequence $S(0),S(S(0),S(S(S(0)),\cdots $ every positive rational numbers appears once and only once.

Therefore if we write $S^n(x)$ for $n^{th}$ iterate of $S$, then we obtain an explicit bijection $F:\mathbb{N}\to \mathbb{Q}^{+}$ by $F(n)=S^n(0) $. The proof is explained in the link I have mentioned above.