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?
 A: Set $\Bbb N = \{1,2,3,4,\dots\}$.
Here we will define a bijective mapping between $\Bbb N$ and the subset of rational numbers
$\quad \Bbb Q_{\gt 0}^{\lt 1} = \{q \in \Bbb Q \mid 0 \lt q \lt 1\}$
For integer $n \ge 1$ define the set
$\tag 1 F_n = \{s/t\in \Bbb Q \mid [s, t \in \Bbb N] \land [t \le n] \land [s \lt t\}]$
We have a chain of inclusions
$\tag 2 \emptyset = F_1 \subset F_2 \subset F_3 \subset \dots \subset F_k \subset \dots $
and denote the union of these sets by $F$; observe that $F = \Bbb Q_{\gt 0}^{\lt 1}$.
Let the number of elements in the set $F_k$ be denoted by $f_k$.
If $k \gt 1$ let $G_k = F_k \setminus F_{k-1}$; observe that $G_k$ has an ordering relation $\le$ defined on it.
We define a function $\Gamma: \Bbb N  \to F$ by the specification
$\quad$ Given $m  \in \Bbb N$
$\quad$ Find $k \in \Bbb N$ such that $f_k \lt m \le f_{k+1}$
$\quad$ Set $\Gamma(m)$ to the
$\tag 3  [m-f_k]^\text{-th} \text{ element of } G_{k+1}$
Exercise: Show that $\Gamma$ is a well defined function that puts the sets into a $\text{1:1 correspondence}$.
See also the wikipedia article Farey sequence.
A: 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.
A: 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.
A: 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.
A: Preliminaries
I will be using the Continued Fraction conception. Firstly, let us consider only rationals that are less than 1. So
$$q < 1, \quad q\in\mathbb{Q}$$
So
every rational $q$ can be written as a continued fraction:
$$q = \cfrac{1}{a_1 + \cfrac{1}{a_2 +\cfrac{1}{a_3 + ...}}} := [a_1, a_2, a_3, ...]$$
Note that none of the $a_i$ is zero and for every $q\in\mathbb{Q}$ its q.f. is of the finite length. Also note that we're using only that kind of q.f.'s in which all the numerators are 1's.
Formula
Let us construct a bijection $\Phi$ between rationals and naturals as follows:
$$\Phi: q \mapsto \prod_{i=1}^{n_q}p_{i}^{a_i - 1},$$
where $n_q$ is the length of q.f. for $q$ and $p_i$ is $i$th prime number. The inverse is straightforward.
Example
$$\Phi\Big(\frac{30}{43}\Big) =  2^03^15^27^3 = 25725$$
This is because
$$\frac{30}{43} = \cfrac{1}{1+\cfrac{1}{2+\cfrac{1}{3+\cfrac{1}{4}}}} := [1,2,3,4]$$ And vice-versa:
$$\Phi^{-1}(225) = \frac{10}{13} = \cfrac{1}{1+\cfrac{1}{3+\cfrac{1}{3}}}$$
This is because
$$225 = 2^03^25^2$$

Of course this works iff there is bijection between those kind of continued fractions and rationals. But it is not too hard to prove.

P.S. I feel that I'm missing something here. Please, verify.
A: I would like to make two comments, both in the direction of dynamics.


*

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



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