Can an explicit formula be found for a bijection $f \colon \mathbb{N} \to \mathbb{Q}$? Let $\mathbb{N}$ be the set of all natural numbers, and let $\mathbb{Q}$ denote the set of all rational numbers. 
Then of course there is a bijection $f \colon \mathbb{N} \to \mathbb{Q}$ since $\mathbb{Q}$ is a countably infinite set. 
Can we find an explicit formula for $f$? 
 A: If you're looking for an explicit function, here's a sequence that maps $\mathbb{N}$ to $\mathbb{Q}^+$, which is almost what you want. Define $f$ as follows:
$$f(1) = 1, \quad f(n + 1) = \frac{1}{\lfloor f(n) \rfloor + 1 - \{ f(n) \}}$$
where $\lfloor x \rfloor$ is the integer part of $x$, and $\{ x \} = x - \lfloor x \rfloor$ is the fractional part. This creates a sequence that hits every rational number.
To show it's a bijection, we relate this function to a binary tree. Miscellaneous facts needed for the proof:


*

*$f(n) \in \mathbb{Q}^+$

*For any real $x$, $y$, if $\lfloor x \rfloor - \lfloor y \rfloor = \{ x \} - \{ y \}$, then $x = y$.

*The Euclidean algorithm works.



First, we show injectivity. Assume there are some $a$ and $b$ in $\mathbb{N}$, with $a < b$, such that $f(a) = f(b)$. If $a \ne 1$, then:
$$
\begin{align*}
\frac{1}{\lfloor f(a - 1) \rfloor + 1 - \{ f(a - 1) \}} &= \frac{1}{\lfloor f(b - 1) \rfloor + 1 - \{ f(b - 1) \}} \\
\lfloor f(a - 1) \rfloor - \{ f(a - 1) \} &= \lfloor f(b - 1) \rfloor - \{ f(b - 1) \} \\
\lfloor f(a - 1) \rfloor - \lfloor f(b - 1) \rfloor &= \{ f(a - 1) \} - \{ f(b - 1) \} \\
f(a - 1) &= f(b - 1)
\end{align*}
$$
Thus, we can descend until we hit $1$. There is some $n > 1$ such that $f(n) = f(1) = 1$. Then $\frac{1}{\lfloor f(n - 1) \rfloor + 1 - \{ f(n - 1) \}} = 1$, implying $\lfloor f(n - 1) \rfloor = \{ f(n - 1) \}$. Because the former is in $\mathbb{N} \cup \{ 0 \}$, and the latter is in $[0, 1)$, both sides must be zero, forcing $f(n - 1) = 0 \notin \mathbb{Q}^+$.

To show surjectivity, we introduce the Stern-Brocot tree. It's a binary tree with root $1$, and if a node has value $\frac{a}{b}$, its left and right children have values $\frac{a}{a+b}$ and $\frac{a + b}{b}$, respectively. If we want to find $\frac{p}{q}$ in the tree, and $p > q$, we look for $\frac{p - q}{q}$, which will have a right child of $\frac{p}{q}$. Similarly, if $p < q$, we look for $\frac{p}{q - p}$. Since this process always terminates at $\frac{1}{1}$, which is definitely in the tree, it must contain all of $\mathbb{Q}^+$.

How did that help? It turns out that if we index the nodes of the tree (breadth-first, left-to-right), this is exactly $f(n)$. To prove it, we show that it satisfies the same recurrence relations.
Claim: $f(1) = \frac{1}{1}$. Proof: trivial.
Claim: $f(n) = \frac{a}{a + b} \implies f(n + 1) = \frac{a + b}{b}$. Proof: plug-and-chug.
Claim: $f(n) = \frac{a}{b} \implies f(2n) = \frac{a}{a + b}$. We proceed by induction. Checking $n = 1$ is easy. For the recursive case, let $s$ such that $b = aq + a - s$ and $0 \le s < a$.
$$
\begin{align*}
f(n) &= \frac{a}{b} \\
&= \frac{a}{aq + a - s} \\
&= \frac{1}{q + 1 - \frac{s}{a}} \\
\frac{1}{ \lfloor f(n - 1) \rfloor + 1 - \{ f(n - 1) \} } &= \frac{1}{\lfloor q + \frac{s}{a} \rfloor + 1 - \{ q + \frac{s}{a} \} } \\
\end{align*}
$$
Thus, $f(n - 1) = q + \frac{s}{a} = \frac{aq + s}{a}$. (Just copy the steps from the injectivity argument.) Now apply the inductive hypothesis, use the theorem above, and then explicitly compute one more iteration:
$$
\begin{align*}
f(n - 1) &= \frac{aq + s}{a} \\
f(2n - 2) &= \frac{aq + s}{(aq + s) + a} \\
f(2n - 1) &= \frac{(aq + s) + a}{a} = q + 1 + \frac{s}{a} \\
f(2n) &= \frac{1}{ \lfloor f(2n - 1) \rfloor + 1 - \{ f(2n - 1) \} } \\
f(2n) &= \frac{1}{ (q + 1) + 1 - \frac{s}{a} } \\
f(2n) &= \frac{a}{ aq + a + a - s } \\
f(2n) &= \frac{a}{a + b} \\
\end{align*}
$$
So the $i$th node has value $f(i)$, showing that the tree is injective and the function surjective.
