Produce an explicit bijection between rationals and naturals

Question

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 1

I would like to make two comments, both in the direction of dynamics.

---

1. Consider the matrices $L=\begin{pmatrix}1&0\\1&1\end{pmatrix}$ and $R=\begin{pmatrix}1&1\\0&1\end{pmatrix}$ which act as shears on the first quadrant $\mathbb{R}_{\geq0}^2$:

Thinking of nonnegative rational numbers as (slopes of rays from the origin through) integer points in $\mathbb{R}^2_{\geq0}$, successive iterates of $L$ and $R$ count $\mathbb{Q}_{\geq0}$:

(A rigorous way of saying/proving this is that $L$ and $R$ freely generate the monoid $\operatorname{SL}(2,\mathbb{Z}_{\geq0})$ of $2\times 2$ matrices with nonnegative integer entries and determinant $1$.)

Choosing an ordering on binary words now produces a bijection $\mathbb{Z}_{\geq0}\to\mathbb{Q}_{\geq0}$. Alternatively one can use some geometric ordering on the "visible points" (e.g. according to polar coordinates).

I have taken the above screenshots from D. Davis' talk "Periodic paths on the pentagon: Swarthmore College Math/Stat Colloquium" (https://youtu.be/5kyundHawJ8; other recordings of the talk seems to be also available); the associated paper is "Periodic paths on the pentagon, double pentagon and golden L" (https://arxiv.org/abs/1810.11310) by Davis & Lellièvre. (They adapt this counting procedure to enumerate closed orbits of billiards on the double pentagon; from the dynamical point of view the above procedure counts the periodic translation trajectories on the square torus or square billiard table.)

Of course this is nothing but the (...-Kepler-...-) Calkin-Wilf tree mentioned above in disguise; indeed, $L(z)$ and $R(z)$ are the two offsprings of $z$.

---

2. The second comment is about the Newman map mentioned above, which is defined by

$$N:[0,\infty]\to[0,\infty],\,\, x\mapsto \begin{cases}0 &\text{, if }x=\infty\\ \dfrac{1}{1-\{x\}+\lfloor x\rfloor}&\text{, otherwise}\end{cases},$$

where $\lfloor x\rfloor$ is the floor of $x$ and $\{x\}=x-\lfloor x\rfloor$ is the fractional part of $x$.

$N$ is a bimeasurable bijection that preserves $\mathbb{Q}_{>0}$. As mentioned above, the orbit of $0$ under $N$ is in one-to-one correspondence with nonnegative rational numbers. Bonanno & Isola, in their paper "Orderings of the rationals and dynamical systems" (https://arxiv.org/abs/0805.2178, Thm.2.3 on p.176), proved that up to a change of coordinates $N$ is the dyadic odometer ( = Von Neumann-Kakutani adding machine) (see e.g. What are the applications of dynamical odometers? or Unclear construction in a paper of Ornstein and Weiss):

Theorem (Bonanno-Isola): Put $\Phi: [0,\infty]\to [0,1], x\mapsto\begin{cases}1&\text{, if }x=\infty\\ \dfrac{x}{x+1}&\text{ otherwise}\end{cases}$, $S=\Phi\circ N\circ \Phi^{-1}$, $?:[0,1]\to[0,1]$ be the (restriction of the) Minkowski question mark function (which is a homeomorphism that is not absolutely continuous) (see e.g. Intuition in understanding Minkowski question mark ?(x) function, Academic reference concerning Minkowski's question mark function), $T$ be the odometer. Then:

(The coordinate change $\Phi$ is also not accidental; it transforms the Stern-Brocot tree into the Farey tree.)

Here is a humble graph (https://www.desmos.com/calculator/rg6xwg5qj1), where $N$ is red, $S$ is blue and (an approximation of) $T$ is green:

Thus we have another geometric way of enumerating the rational numbers using the odometer ($0$ is sent to $0$ by $?\circ \Phi$). Arguably it's easier to iterate $T$ than $N$.