18
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Related: math.stackexchange.com/q/424654/622 and math.stackexchange.com/q/7643/622 $\endgroup$ – Asaf Karagila Mar 21 '15 at 21:18
  • 6
    $\begingroup$ Frode, do you have an intended precise meaning of "natural" here? People often use that word as a means to reject (counter)examples that they don't favor (they are not natural), and usually in such cases I don't find the word to have a very robust meaning. $\endgroup$ – Joel David Hamkins Mar 21 '15 at 21:22
  • 3
    $\begingroup$ This question has been closed for a few hours (as unclear) yesterday and then quickly reopened. For this kind of questions of very basic level I understand that there's a large number of upvotes, and hence of people who voted to reopen it, but it definitely not a mathematical research question, nor is it a precise question (it isn't much more precise than "what is the most beautiful tiling of the plane"?) And, as mentioned by Asaf, it is a double duplicate of questions in MathStackEchange. $\endgroup$ – YCor Mar 22 '15 at 9:09
  • 2
    $\begingroup$ @YCor It is true that some who found the question imprecise voted to close it yesterday. The fact that several knowledgeable people have come up with clear and interesting converging answers suggests that the question is not imprecise to such a degree as you suggest. One should to my mind be somewhat cautious with respect to dismiss questions as not relevant to mathematical research. To me it e.g. seems clear that an explicit function is of interest for making some codings of syntax with special properties. $\endgroup$ – Frode Bjørdal Mar 22 '15 at 16:58
  • 4
    $\begingroup$ If one is willing to consider the prime factorisation coming from the fundamental theorem of arithmetic as "natural", then the problem reduces to finding a "natural" bijection between the non-negative integers and the integers, which maps 0 to 0. $\endgroup$ – Terry Tao Mar 24 '15 at 15:09
37
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ That is a beautiful result if it is true, and I would have liked to see the proofs. I assume that $f(0)$ is meant to be $0$; is that right? Notice that you do not define k and s. $\endgroup$ – Frode Bjørdal Mar 22 '15 at 1:14
  • 4
    $\begingroup$ 1. I actually always prefer to view it as a bijection between positive integers and positive rationals, although I suppose that the most conventional notation would suggest that $\mathbb{N}$ and $\mathbb{Q}^+$ both contain zero, in which case it is sensible to also put $f(0)=0$. 2. I made a misprint which made $k$ non-uniquely defined, I shall correct it now. The convention $q_s=1$ chooses the unique of two possible continued fraction expansions, so $s$ is implicitly defined. 3. Once formulated, this result is fairly easy to prove inductively. Let me know if you require it, I can do it later. $\endgroup$ – Vladimir Dotsenko Mar 22 '15 at 1:31
  • 5
    $\begingroup$ The proof can perhaps be presented a bit more conceptually. Uniqueness of continued fraction forms is easily seen to be equivalent to the statement that each non-negative rational is uniquely reachable, starting from 0, by some sequence of the two operations “add 1”, or “add 1 and invert”. This gives a bijection between non-negative rationals and binary sequences. On the other hand, the usual binary representation gives a bijection between binary sequences and non-negative integers. The function $f$ is the composite of these two bijections. $\endgroup$ – Peter LeFanu Lumsdaine Mar 23 '15 at 12:25
  • 2
    $\begingroup$ @VladimirDotsenko: yes, I absolutely agree that your details are good to give, and important for a full proof. But it is often helpful to have a higher-level explanation as well as the details. $\endgroup$ – Peter LeFanu Lumsdaine Mar 23 '15 at 13:26
  • 4
    $\begingroup$ Incidentally, this sequence representation is nicely related to the one underlying Calkin-Wilf. This representation obtains positive rationals using the operations $a$, “add one”, and $i$, “add one, then invert”; Calkin-Wilf instead uses $a$ together with $j$, “invert, then add one, then invert”. These satisfy identities $i(a(x)) = j(i(x))$, $i(i(x)) = j(a(x))$. So one can convert from this representation to Calkin-Wilf by crawling from the outside in: e.g. $2/5 = i(a(i(1)) = j(i(i(1)) = j(j(a(1))$. In particular, these two representations of a rational always have the same length. $\endgroup$ – Peter LeFanu Lumsdaine Mar 23 '15 at 15:10
38
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ If you take a look at Theorem 1 of this paper, you can see how to get the n-th element directly (modulo solving a counting problem). $\endgroup$ – Burak Mar 21 '15 at 21:09
  • 7
    $\begingroup$ I took the liberty of adding images of the tree. $\endgroup$ – Joel David Hamkins Mar 21 '15 at 21:10
  • $\begingroup$ @JoelDavidHamkins: Thanks Joel! I was about the edit the first sentence anyway. $\endgroup$ – Burak Mar 21 '15 at 21:11
  • $\begingroup$ Oh, sorry if I stepped on your toes. I had made another edit to add the breadth-first enumeration, which is now gone. Shall I put it back? $\endgroup$ – Joel David Hamkins Mar 21 '15 at 21:13
  • 4
    $\begingroup$ @JoelDavidHamkins: Feel free to edit in any way you think would help future visitors of this post! $\endgroup$ – Burak Mar 21 '15 at 21:14
15
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ By the way, I want to emphasize that the entire set-up is really nothing but an explicit recursive description of a bijection $\mathbb{N} \to \omega^\omega$, where the right side is a countable ordinal representing a set of finite sequences of integers in lexicographic order (each sequence of even length, so that we don't accidentally double count rationals, e.g., $[2]$ and $[1; 1]$ are two continued fraction representations of $2$). $\endgroup$ – Todd Trimble Mar 22 '15 at 14:27
8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.