increasing bijection - MathOverflow

increasing bijection

2009-11-21T00:47:10Z

Using the back-and-forth method we can construct an increasing bijection from the set of rational numbers to the set of of rational numbers except zero.

http://en.wikipedia.org/wiki/Back-and-forth_method

I would like to have a "natural" bijection. The algorithm resulting from the back-and-forth method behaves rather chaotically.

It would be nice for example to have an uniform bound on the number of steps needed to evaluate the image of any given rational number $a=\frac{p}{q}$. I'm note sure what should count as a "step" here, maybe adding or multiplying integers.

Answer by Foo for increasing bijection

2009-11-21T01:47:53Z

Choose sequences of rational numbers $a_i$ and $b_i$ strictly monotonically converging to $\sqrt{2}$ from below and above. Map $a_i$ to $-1/i$ and map $b_i$ to $1/i$. Extend linearly. This meets your criteria, if we allow ourselves to "know" where $p/q$ is with respect to the $a_i$ and the $b_i$.

Answer by sdcvvc for increasing bijection

2009-11-21T20:55:23Z

The Stern-Brocot tree gives a representation of (Q⁺,<) as infinite binary search tree. One can create another infinite binary search tree with 0 on top, positive rationals on right and negative ones on left. This gives a representation of (Q,<) as an infinite binary search tree. If we remove 0, then we get a sum of two trees ("two trees side by side"). The problem is to create an order isomorphism between the tree corresponding to (Q,<) and sum of two trees corresponding to (Q-{0},<).

These two trees can be merged into one as follows: let root(T), left(T), right(T) be the root, left subtree and right subtree of a tree T. The merge is defined recursively by:

                                root(T1)
merge(T1,T2) =                 /       \
                          left(T1)   root(T2)
                                      /    \
               merge(right(T1),left(T2))   right(T2)

(to be precise, this definition is coinductive)

The Stern-Brocot tree is Euclidean algorithm inside, so complexity aspect you seem to be interested in should be easy. [Foo's answer gives probably much easier analysis; I just wanted to show the combinatorial "look" at the linear orders.]