# 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?

-
Do you need a formula or does the picture and explanation in en.wikipedia.org/wiki/… suffice? See also en.wikipedia.org/wiki/… – lhf Oct 24 '10 at 3:10
I wasn't familiar with pairing functions, so let me look at that more closely. My professor insisted, though, that I come up with a formula, and of course that would also require that equivalent pairs (in the rational number sense) shouldn't get counted more than once. – Alex Basson Oct 24 '10 at 4:55
@lhf. Maybe you should post your comment as an answer; otherwise, it's not unlikey that this question remains unanswered. – a.r. Oct 24 '10 at 5:21
Could you provide a list of features that you consider legitimate to include in your formula? Often when these questions are posed, responses are met with "that doesn't count as a formula." – Douglas S. Stones Oct 24 '10 at 5:43
Don't know if it would count as "explicit" but every rational number occurs exactly one in the Calkin-Wilf sequence en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree – Jyotirmoy Bhattacharya Oct 24 '10 at 6:42

Wikipedia contains several explicit examples: Cantor pairing function, Stern–Brocot tree, Calkin–Wilf tree.

-
Am I missing something or is the Cantor pairing function is not a bijection between the rationals and the naturals? It seems to, at best, reduce our problem to finding a bijection between $\mathbb{Q}$ and $\mathbb{N} \times \mathbb{N}$ – nham Apr 30 '13 at 5:14
Indeed, none of these are bijections between $\mathbb N$ and $\mathbb Q$, at least, not in the sense of "explicit." – Thomas Andrews Dec 14 '14 at 16:31

I'll assume $\mathbb N$ contains $0$.

Define the a bijection $s:\mathbb N\to \mathbb Z$ as:

$$s(n)=\begin{cases} 0&n=0\\ (-1)^n\left\lfloor\frac{n+1}{2}\right\rfloor&n>0 \end{cases}$$

So, the sequence would be $0,-1,1,-2,2\dots$.

Then for any $n$, define $\rho(n)=p_1^{s(a_1)}p_2^{s(a_2)}\cdots p_k^{s(a_k)}$, where:

$$n+1=p_1^{a_1}\cdots p_k^{a_k}$$

Where the $a_i$ are possibly zero.

This is a bijection of the natural numbers with $\mathbb Q^+$.

Then define $$\rho_1(n)=\begin{cases} 0&n=0\\ (-1)^n\rho\left(\left\lfloor\frac{n-1}{2}\right\rfloor\right)&n>0 \end{cases}$$

for a bijection between $\mathbb N$ and $\mathbb Q$.

For example, if $n=19$, then $n+1=2^2\cdot 3^0\cdot 5^{1}$ and $\rho(19)=2^{-1}\cdot 3^0\cdot 5^{1} = \frac{5}{2}$.

(Defining for positive $n$ the function $f(n)=\rho(n-1)$, we actually have that $f$ is multiplicative - $f(mn)=f(m)f(n)$ of $m,n$ relatively prime. So we get that $f(p^{2k})=p^k$ and $f(p^{2k-1})=p^{-k}$.)

Basically, every positive integer has a unique representation as:

$$p_1^{a_1}p_2^{a_2}\dots$$

where the $p_i$ are all primes, the $a_i$ are non-negative integers, and all but finitely many of the $a_i$ are zero.

The rational numbers have the same representation, with the only change that the $a_i$ are integers, possibly non-negative.

-
Why hasn't this been upvoted more? Good answer! (+1) – fancynancy Feb 16 '15 at 17:46
For your bijection between $\mathbb{N}$ and $\mathbb{Q}$, why have you defined it as $\rho_1$ instead of just $\eta$ or something else (I don't see anything to indicate significance of the index)? – fancynancy Feb 16 '15 at 17:52
@fancynancy I think just because it was a variant of $\rho$. I think the function I now call $\rho_1$ was just called $\rho$, but then I realized I needed the intermediate function, which was more "important" in some way, so I called that $\rho$ and renamed this $\rho_1$. It's just a function name. – Thomas Andrews Feb 16 '15 at 18:13
That's what I thought--just wanted to make sure. Thanks for clarifying. – fancynancy Feb 16 '15 at 18:17

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.

-

This is a bijection between the Stern-Brocot tree and the tree of Natural numbers. Every left node is given by $L_n = [2 P_n ]$ and every right one by $R_n= [2 P_n +1 ]$ where $P_n$ is the value of the parent node and $P_0=[1]$. We have the sequence of transformations $P_n \rightarrow [ L_n , R_n ]$, $L_n \rightarrow P_{n+1}$, $R_n \rightarrow P^\prime_{n+1}$ .

In list notation for the tree (count the brackets) this is

$$n = 1 \mapsto [1,[2],[3]]$$

$$n = 2 \mapsto [1,[2,[4], [5]], [3,[6], [7]]]$$ $$n = 3 \mapsto [1,[2,[4,[8],[9]],[5,[10],[11]]],[3,[6,[12],[13]],[7,[14],[15]]]]$$ and so on.

-

In order to create this function, one needs to look at this in several parts and then assemble the pieces together to produce the final function.

First you'll need the following series:

0,1,1,2,1,2,3,1,2,3,4,...

0,1,2,1,3,2,1,4,3,2,1,...

One series is the numerator and the other the denominator. An explicit function to generate each series will be needed (try wikipedia or other online math resources to find these)

Then a way to cycle through this a second time so that all values are negative will be needed.

The easiest way to think of assembling all these parts is most likely composite functions.

Use the old (-1)^n trick for switching to negative values.

A professor showed me this function once, I've been trying to look for it in old notes but to no avail. If I remember correctly, it uses composite functions and floors/ceilings.

$f(\frac{a}{b})=\frac{1}{2}(a+b-2)(a+b-1) + a$ with the usual arrangement of the rationals. Don't reduce the fractions in the list.
Example: $f(\frac{3}{6}) = \frac{1}{2}(3+6-2)(3+6-1) + 3 = 31$.
But if you don't reduce the fractions, then it isn't a bijection anymore. In fact it's not even a function, since $f(\frac{1}{2}) \neq f(\frac{3}{6})$. – Alex Basson Dec 23 '14 at 15:55