Is there a natural bijection from $\mathbb{N}$ to $\mathbb{Q}$?

Question

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

Answer 1

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

Answer 2

I believe the Calkin-Wilf sequence would work for you. We can construct the Calkin-Wilf binary tree so that the root is $1/1$, and the children of $a/b$ are $a/(a+b)$ and $(a+b)/b$, in order. This contains all positive rationals exactly once, and the path to the root from $p/q$ follows a slow version of Euclid's algorithm for finding the GCD of $p$ and $q$: $(p,q) \mapsto (p-q,q) \textrm{or} (p,q-p)$. A breadth first search through the tree visits the nodes in the order of the Calkin-Wilf sequence.

Besides the recursive definition that gives you this sequence, you can get the $n$th element directly modulo solving a counting problem that is mentioned in the paper I linked in the comments. Specifically, let $b(n)$ count the number of ways that $n$ can be written as a sum of powers of $2$ so that each power is used at most twice. This is also called $\operatorname{fusc}(n+1)$. For example, $b(4)=3$ because $4=4=2+2=2+1+1$, and $b(5)=2$ because $5=4+1=2+2+1$. $\lbrace b(i) \rbrace_{i=0}^\infty = \lbrace 1,1,2,1,3,2,3,1,4,3,5,...\rbrace$. Then $n \mapsto b(n)/b(n+1)$ gives us the bijection sending $0,1,2,3,...$ to $\frac{1}{1},\frac{1}{2},\frac{2}{1},\frac{1}{3},\frac{3}{2},...$.

I always found this to be a cool bijection between naturals and positive rationals.

Answer 3

To my aesthetic sensibilities, the Calkin-Wilf tree response is pretty close to optimal, but I'll add some additional glosses. (I only noticed later that Vladimir Dotsenko wrote something similar before me.)

As you can see, the Calkin-Wilf tree is an infinite binary tree; each node of the tree can be identified by a word or finite sequence of letters using the alphabet $\mathbb{2} := \{L, R\}$. There are of course lots of ways of setting up explicit bijections between the set of nodes of this tree and $\mathbb{N}$. The spiral depicted in Burak's answer suggests one possibility; roughly speaking, this is the ordinal sum $\mathbb{2}^0 + \mathbb{2}^1 + \mathbb{2}^2 + \ldots$ where shorter words always precede longer words but words of the same length are ordered according to the dictionary, where letter $L$ precedes letter $R$. Thus the empty word (of length 0) comes first, then $L, R$, then $LL, LR, RL, RR$, etc. A more or less explicit enumeration from $\mathbb{N}_+ = \{1, 2, 3, \ldots\}$ to the set of words (the free monoid $\mathbb{2}^\ast$) is just by binary representation, where each number has a leading $1$ followed by a sequence of "digits" $L$ (the digit zero) and $R$ (the digit $1$).

Meanwhile, by the Euclidean algorithm, each positive rational may be uniquely specified as a continued fraction $[a_0; a_1, \ldots, a_n]$ where $n$ is odd and $a_0$ may be $0$; the remaining $a_i$ are positive integers (N.B.: we allow for the possibility that $a_n = 1$!). More exactly, we define $R^a$ to be the operator $R^a(x) = a + x$ and $L^a$ to be the operator $L^a(x) = \frac1{a + \frac1{x}}$ (note that $L$ is a conjugate of $R$), and we identify a positive rational by a unique expression $q = R^{a_0} L^{a_1} \ldots L^{a_n - 1}(1)$. The word on the right-hand side is precisely the Calkin-Wilf representation using the alphabet $\mathbb{2} = \{L, R\}$.

There are actually a number of fascinating representations along similar continued fraction lines; I could write more, but for now you can read the nLab article. Noam Zeilberger wrote up the section on Calkin-Wilf, and there is also material there on the categorical perspective which involves treating the positive rationals as an initial algebra for a suitable endofunctor, if you want some "natural" perspective.

Answer 4

There is an interesting bijection between the factorial numbering system and the interval of rationals $[0,1)$. Factorials replace powers in the factorial system. $321_! = 3 \cdot 3! + 2 \cdot 2! + 1 = 23_{base10}$. The numerals in each position are limited by the factorial. Only 0 and 1 can be in the first position; 0, 1, or 2 in the second position; 0-3 in the third, etc.

Similarly, we can write fractions using the inverses $\frac{1}{2!}, \frac{1}{3!}, \frac{1}{4!}$. $0.123_! = \frac{1}{2!} + \frac{2}{3!} + \frac{3}{4!} = \frac{23}{24}$. Every rational number has a unique finite representation in the factorial numbering system. We can count in factorial, 1, 10, 11, 20, 21, ..., and take the "inverse" to get a bijection with the rationals in $[0,1) : .1 = \frac{1}{2}, .01 = \frac{1}{6}, .11= \frac{2}{3}, .02 = \frac{1}{3}, .12 = \frac{5}{6}, .001 = \frac{1}{24}$ etc.

The factorial numbering system is just one of many product based numbering systems that have a unique finite representation for every rational number.