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".

Solution 1:

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

Solution 2:

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.