# 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 at 16:31

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.

Sorry if this was not helpful to you in your pursuits.

-

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}$.)

-