In a conversation where it came up that the Pythagoreans probably found an enumeration of the rational numbers I erroneously remarked that Georg Cantor found a natural bijection from $\mathbb{N}$ to $\mathbb{Q}$ with his pairing function. Is there a natural bijection bethween these sets?


Naturalness is of course not a precise criterion. But we may distinguish between degrees of naturalness and say that a bijection $f$ between $\mathbb{N}$ and $\mathbb{Q}$ is more natural than another bijection $g$ between these sets if for the identity statements $f(n)=\alpha(n)$ and $g(n)=\beta(n)$ the formula $\alpha(n)$ is lower in the arithmetical hierarchy than formula $\beta(n)$. Also, $f$ is more natural than $g$ if the formula $\alpha(n)$ is shorter than the formula $\beta(n)$. 



Is there a natural bijection from $\mathbb{N}$ to $\mathbb{Q}$?
There is a following result which is quite lovely, I think (I don't remember right away whose result this is):


Let us define a function $f\colon\mathbb{N}\to\mathbb{Q}^+$ as follows: $f(1)=1$, and also $f(2n)=f(n)+1$, $f(2n+1)=\frac{1}{f(n)+1}$. Then:


1. $f$ is a bijection (Sketch of a proof: A. Show using induction on $m$ that we have $f(n)\ne f(m)$ for $n\ne m$. B. Show that $f$ is surjective, that is for each continued fraction $q=[q\_0;q\_1,\ldots,q\_s]$ there exists $n$ for which $f(n)=q$, this is done using induction on $q\_0+q\_1+\cdots+q\_s$);
2. The binary expansion $n=2^{m\_0}+2^{m\_1}+\cdots+2^{m\_k}$ with $0\le m\_0<\cdots<m\_k$ and the continued fraction expansion $f(n)=q\_0+\cfrac{1}{q\_1+\cfrac{1}{q\_2+\cdots}}=[q\_0;q\_1,q\_2,\ldots,q\_s]$ chosen in the way that $q\_s=1$, are related as follows: $s=k+1$, and for all $i=0,\ldots,k$ we have $m\_i=q\_0+\cdots+q\_i$. (This is easily proved by induction on $n$).


