# Order preserving bijection from $\mathbb Q\times \mathbb Q$ to $\mathbb Q$

Do you have a simple example of order preserving bijection from $\mathbb Q\times \mathbb Q$ to $\mathbb Q$?

On $\mathbb Q$, I use the usual order and on $\mathbb Q\times\mathbb Q$, I define the order as : $$(a_1,b_1)<(a_2,b_2) \mbox{ iff either}\left\{\begin{array}{l} a_1<a_2\\ a_1=a_2\mbox{ and } b_1<b_2\\ \end{array}\right.$$

As $\mathbb Q\times \mathbb Q$ and $\mathbb Q$ are both dense countable sets, they are order isomorphic, and I know I can build an order preserving bijection between them using bijections with $\mathbb N$ and a zig-zag like induction, but I was wondering if something simpler could be given, more analytic.

EDIT :

An example of zig-zag like induction is :

1. take a bijection from $\mathbb N$ to $\mathbb Q$, and say $a_i$ the $i^{th}$ element of $\mathbb Q$.
2. take a bijection from $\mathbb N$ to $\mathbb Q\times \mathbb Q$ and say $b_i$ is the $i^{th}$ element of $\mathbb Q\times \mathbb Q$.
3. Build your order preserving bijection $f$ by
1. On step $0$ : $f(a_0)=b_0$
2. On step $(2n+1)$ : $f(a_k)=b_j$ where $k$ is the smallest integer such that $a_k$ was not chosen in the previous steps, and $j$ is the smallest integer such that $b_j$ was not chosen and $f$ is still order preserving.
3. On step $(2n+2)$ : $f(a_k)=b_j$ where $j$ is the smallest integer such that $b_j$ was not chosen in the previous steps, and $k$ is the smallest integer such that $a_k$ was not chosen and $f$ is still order preserving.
4. After all steps (in $\mathbb N$), $f$ is indeed an order preserving bijection, but it's not what I mean by "simple".
• I’m not sure they are isomorphic in the sense you mean. Different countable ordinals (aka order types) may not be isomorphic. In set theory, $\omega$ and $\omega+1$ are both countable but not isomorphic. – Ewan Delanoy Oct 28 '13 at 14:35
• All dense countable sets without extremum are order isomorphic, this is a well know result. However, I don't remember who gave his name to this result. Cantor ? – Xoff Oct 28 '13 at 14:37
• That's true, @Ewan, but countable dense linear orders without least or greatest element are necessarily order-isomorphic. (Result due to Cantor, I believe.) Well-ordered sets are more stringent with isomorphism. – Cameron Buie Oct 28 '13 at 14:38
• Have you tried to write down the function which comes from the usual zig-zag construction? – Martin Brandenburg Oct 28 '13 at 14:50
• It depends of the bijection with $\mathbb N$ that you decide to use. I do not know if some bijections yield simple result. – Xoff Oct 28 '13 at 14:56

## 2 Answers

There is a natural order isomorphism from $\Bbb{Q}$ to the surreal numbers up to generation $\omega$, where instead of getting the average of two adjacent numbers in the previous generation, you use the mediant operation $\frac ab\oplus\frac cd=\frac{a+c}{b+d}$. The surreal numbers themselves can be represented as finite sequences of $\pm1$'s, with lexicographic ordering, and where different length strings are compared as $$\langle a_1,\dots,a_i,-1,b_1,\dots,b_j\rangle<\langle a_1,\dots,a_i\rangle<\langle a_1,\dots,a_i,+1,c_1,\dots,c_k\rangle.$$

(Alternatively, you can view them as functions $g:\Bbb N\to\{-1,0,1\}$ such that $\{x\in\Bbb N:g(x)\ne0\}=\{1,2,\dots,n\}$ for some $n$, with the standard lexicographic order. This is the same as the finite string version, except we "pad with zeroes" at the end.) We can picture this space as an infinite binary tree, with the vertices being the rational numbers, and with the ordering putting each root between the left and right subtrees. As an illustration of the mapping, I give a few examples:

$$\begin{array}{ll} \langle\rangle\mapsto0/1&\langle+,-\rangle\mapsto1/2\\ \langle+\rangle\mapsto1/1&\langle+,+,-\rangle\mapsto3/2\\ \langle-\rangle\mapsto-1/1&\langle+,-,-\rangle\mapsto1/3\\ \langle+,+\rangle\mapsto2/1&\langle+,-,-,+\rangle\mapsto2/5\\ \langle+,+,+\rangle\mapsto3/1&\langle+,-,-,+,+\rangle\mapsto3/7\\ \end{array}$$

I think this is called a "Farey tree" or "mediant tree" or something. The important part is that this simplifies the question of ordering on $\Bbb Q$ to ordering on this tree space, which is much simpler. Now since the ordering is just lexicographic on the strings, we can just interleave two such orderings as follows:

Suppose we are encoding the pair $\langle a_1,\dots,a_i,a'_1,\dots,a'_j\rangle;\langle b_1,\dots,b_k,b'_1,\dots,b'_l\rangle$, where the $a$'s and $b$'s are $\pm1$. The substring $a_1,\dots,a_i$ is the longest initial string which have all values equal; that is $a_1=a_2=\dots=a_i\ne a'_1$. (If all the $a$'s are the same, then $j=0$.) Similarly, $b_1,\dots,b_k$ is the longest substring such that $b_1=b_2=\dots=b_k\ne b'_1$. Then we have the following:

$$f(a,\langle\rangle)\equiv\langle a_1,\dots,a_i,a'_1,-a'_1,a'_2,-a'_2,\dots,a'_j,-a'_j\rangle$$ $$f(a,\langle b_1\rangle)\equiv f(\langle a_1,\dots,a_i,a'_1,\dots,a'_j,b_1\rangle,\langle\rangle)\sqcup\langle -b_1\rangle$$ $$f(a,b)\equiv f(a,\langle b_1\rangle)\sqcup\langle b_2,-b_2,b_3,-b_3,\dots,b_k,-b_k,b'_1,\dots,b'_l\rangle$$

where $\sqcup$ is the sequence concatenation function. Since we have the same values in the same order, except that some values have had $\alpha\mapsto\langle\alpha,-\alpha\rangle$, which is still lexicographically in order, this is an order homomorphism. It is less obvious that this is bijective, but the inverse function is also difficult to describe, so I'll leave that as an exercise for the reader. It helps to draw a picture of the trees. Here are some examples:

$$\begin{array}{ll} \langle\rangle;\langle\rangle\mapsto\langle\rangle&\langle\rangle;\langle+,-\rangle\mapsto\langle+,-,-\rangle\\ \langle+\rangle;\langle\rangle\mapsto\langle+\rangle&\langle\rangle;\langle+,+,+\rangle\mapsto\langle+,-,+,-,+,-\rangle\\ \langle\rangle;\langle+\rangle\mapsto\langle+,-\rangle&\langle+,-,-,-\rangle;\langle\rangle\mapsto\langle+,-,+,-,+,-,+\rangle\\ \langle+,+\rangle;\langle\rangle\mapsto\langle+,+\rangle&\langle+,+,+\rangle;\langle+,+,+\rangle\mapsto\langle+,+,+,+,-,+,-,+,-\rangle\\ \langle+,-\rangle;\langle\rangle\mapsto\langle+,-,+\rangle&\langle+,+,-\rangle;\langle-,-,+,-\rangle\mapsto\langle+,+,-,+,-,+,+,-,+,+,-\rangle\\ \end{array}$$

Note examples 2 and 3 in the second column: the numbers $(1/n,0)$ (which map to $\langle+,-^n\rangle;\langle\rangle$) are represented by alternating signs ending in a $+$, while $(0,n)$ (which maps to $\langle\rangle;\langle+^n\rangle$) gives the same sequence of alternating signs, except it ends in a $-$. Thus these two sequences approach each other (as we would expect!) but there is no point in the middle, which would be represented by $\langle+,-,+,-,\dots\rangle=\varphi^{-1}$, the golden ratio. Indeed, it is curious (but of course essential) that each rational number $r$ has an open interval corresponding to the image of $f(r\times\Bbb Q)$ in the target space (also $\Bbb Q$) which are (a) disjoint and (b) in the same order as the numbers themselves, so the closure of $f(\Bbb Q\times0)$ is a nullset (the numbers are so "spaced out" that they have few limit points). By the observation above, we know that $f(0\times\Bbb Q)=\Bbb Q\cap (-\varphi^{-1},\varphi^{-1})$.

Edit: I'll see if I can give a few more hints on how to recognize this function as a bijection on the tree space. I prefer to start by identifying the lexicographic binary tree space with what I call $Q$-trees, whose vertices may have either $2$ or $4$ children. An (infinite) $Q$-tree is defined as a root with four children. In order, we have a left $Q$-tree, then a binary tree, then the root, then another binary tree, and finally another $Q$-tree. A point in this tree can be identified by a finite sequence of $\{\pm1,\pm2\}$, but by the construction, once you choose $\pm1$, you are in a binary tree and can no longer choose $\pm2$. Thus each such string is of the form $\langle a_1,\dots,a_m,b_1,\dots,b_n\rangle$ where $a_i=\pm2$ and $b_i=\pm1$, and it is obvious that this space is order isomorphic to pairs in the binary tree space via $\langle a_1,\dots,a_m\rangle;\langle b_1,\dots,b_n\rangle\mapsto\langle 2a_1,\dots,2a_m,b_1,\dots,b_n\rangle$.

Now suppose we are given $c=\langle c_1,\dots c_n\rangle$ from the range, and wish to find $a=\langle a_1,\dots,a_n\rangle$ such that $f(\langle\frac12a_1,\dots,\frac12a_m\rangle,\langle a_{m+1},\dots,a_n\rangle)=c$ (where $a_1,\dots,a_m\in\{\pm2\}$ and $a_{m+1},\dots,a_n\in\{\pm1\}$). On a first pass, we can identify the first element $a_1$: if $c=\langle\rangle$ then $a=\langle\rangle$, and if $c_1=-1$ then use $-f^{-1}(c)=f^{-1}(-c)$ to reduce to the case $c_1=1$. Now we can take advantage of the known ordering on the binary tree space to say that $a_1=2$ iff $c>\langle+,-,+,-,\dots\rangle$ (this is not actually an element of the space, but you can read it as $c>\langle+,-\rangle^n$ for all $n$).

To identify subsequent elements, we can recurse down the tree. If $a_1=2$, then the child is another $Q$-tree, so consider the following map, also defined by recursion. Let $g(\langle+\rangle)=\langle\rangle$, $g(\langle+,+\rangle\sqcup a)=\langle+\rangle\sqcup a$, and $g(\langle+,-\rangle\sqcup a)=\langle-\rangle\sqcup g(a)$. Then $g$ is a bijection from the set of all points greater than $\langle+,-,+,-,\dots\rangle$ to all points in the tree, and we let $f^{-1}(c)=\langle+2\rangle\sqcup f^{-1}(g(c))$ in this case.

If $a_1=1$, then consider the map $h(\langle+,-\rangle)=\langle\rangle$, $h(\langle+,-,-\rangle\sqcup a)=\langle-\rangle\sqcup a$, and $h(\langle+,-,+,-\rangle\sqcup a)=\langle+\rangle\sqcup h(\langle+,-\rangle\sqcup a)$. This is a bijection from points between $\langle\rangle$ and $\langle+,-,+,-,\dots\rangle$ to the whole space, and then $f^{-1}(c)=\langle+1\rangle\sqcup h(c)$ in this case. (Note that since this child is a binary tree and not a $Q$-tree, we don't call $f^{-1}$ recursively here.)

Now the exercise for the reader is to show that this is in fact the inverse to $f$.

• I love "On numbers and games" by J.H.Conway. Your solution is very elegant ! Now, I wonder if it can be used to design some Hackenbush variant :) – Xoff Oct 30 '13 at 8:34
• For those who wondered, this is the Minkowski's question mark function (en.wikipedia.org/wiki/Minkowski's_question_mark_function) that is used at the beginning of this answer. – Xoff Oct 30 '13 at 11:11
• I assume you are referring to the remark about using the mediant instead of the arithmetic mean in computing the "descendant" of two earlier-generation surreal numbers, since it looks from a cursory examination that $?(x)$ maps rationals to dyadic rationals, which can then be interpreted as surreal numbers. Also, the term I was looking for was Stern-Brocot tree, not "Farey tree" (although it is closely related to "Farey sequences"). – Mario Carneiro Oct 30 '13 at 11:56
• (Actually, my function is an extension of the Stern-Brocot tree from positive rationals to all rationals by adding another level at the top: the right branch is the regular Stern-Brocot tree, the left branch is the negative of the right branch, and the root is 0. This way we get every rational number.) – Mario Carneiro Oct 30 '13 at 12:07
• I'm convinced this is indeed a bijection ! – Xoff Oct 31 '13 at 11:20

Here is a rough idea of how to construct an order-preserving injection between the rational points in $(0,1) \times (1,2)$ and those in $(0,1)$. It is not difficult to identify an open interval with $\mathbb{Q}$ in a very analytic way, so this can be modified to give injection $\mathbb{Q} \times \mathbb{Q} \to \mathbb{Q}$. This is of course far from answering the original question. [Edit: this is in fact quite difficult; but we can go from the open intervals to $\mathbb{Q}_+ \times \mathbb{Q}_+ \to \mathbb{Q}_+$].

Recall that each rational $q$ has a finite continued fraction expansion $q = [a_0;a_1,\dots,a_k,1] = a_0+1/(a_1+1/(a_2+\dots)))$, where $a_0 \in \mathbb{Z}$ and $a_i\in \mathbb{N}$ ($0 \not \in \mathbb{N}$ here) for $i>0$. The term $a_0$ identifies the unit interval where $q$ lies: $q \in [a_0,a_0+1)$. With this identification, the order on $\mathbb{Q}$ corresponds to the lex order on $\mathbb{Z} \times\mathbb{N} \times \mathbb{N} \dots$, which is not quite obvious, but can be easily deduced from what is known about approximation of numbers by continued fractions.

For any points $q = [0;a_1,\dots,a_k,1] \in (0,1)$, and $r= [1;b_1,\dots,b_l,1] \in (1,2)$, define $f(q,r) = [0;2a_1,2a_2,\dots,2a_k,1,b_1,\dots b_l,1]$. Clearly, this gives a well defined continued fraction for any $q,r$. To see that this preserves the order, it is enough to look at the lexicographic orders in the fraction expansions. The only situation when we run into trouble is when we are comparing numbers with different lengths of expansion. However, note that the factor $2$ by which all the $a_i$'s are multiplies ensures that if we are comparing $(q,r)$ with $(q',r')$ and $k<k'$, then in expansion of $f(q,r)$ at $k+1$-th position we hit $1$ which is strictly smaller than $2a'_{k+1} \geq 2$ --- hence the order is preserved in this case. Injectivity is obivious from monotonicity.

• How 'very analytic' can you be? Are there continuous order-preserving rational maps from e.g. $(0,1)\mapsto(-\infty,\infty)$? My initial obvious attempts don't seem to work... – Steven Stadnicki Oct 28 '13 at 18:22
• @StevenStadnicki: My bad. I had in mind identifying $(0,1)$ with $(-\infty,\infty)$ by a map like $x \mapsto \frac{1}{x} - \frac{1}{1-x}$, but overlooked the obvious fact that it's not a bijection when restricted to the rationals. Of course, we can change $(0,1)$ to $(0,\infty)$ by a map like $x \mapsto \frac{1}{1-x} -1$, but that's not quite where we want to go. – Jakub Konieczny Oct 28 '13 at 18:34
• exactly - you can easily get 'piecewise rationality', which IMHO is fine for explicitness, but I don't think you can actually get a single rational bijection from a finite open interval to all of $\mathbb{Q}$. (Of course, there are elementary bijections from finite open intervals to $\mathbb{R}$, but those are a different matter) – Steven Stadnicki Oct 28 '13 at 18:42
• I think that $\frac{x}{1+|x|}$ is a bijection from $\mathbb Q$ to $(0,1)\cap\mathbb Q$. – Xoff Oct 28 '13 at 19:21
• What bothers me is that $x\mapsto[0;2x;\dots]$ is a decreasing function whereas $x\mapsto[0;a;2x;\dots]$ is an increasing function. I think it could be a problem when you mix $q$ of different lengths. – Xoff Oct 28 '13 at 19:24