Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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

4 Answers 4

up vote 17 down vote accepted

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

share|improve this answer
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

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:



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.

share|improve this answer

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:


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 natural numbers have the same representation, with the only change that the $a_i$ are integers, possibly non-negative.

share|improve this answer

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

This formula was found in "Introduction to Abstract Mathematics" by John F. Lucas.

share|improve this answer
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
You are right Alex. The formula was presented as a way of showing that the rationals are countable. –  Gary Adams Dec 23 '14 at 16:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.