# increasing bijection

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.

-
Do you mean "naturals without zero"? I haven't seen any mention of the exact bijection you mention. –  Jason Dyer Nov 21 '09 at 3:35
@Jason: I don't think "naturals" was meant. See the link given to something much more general. –  Jonas Meyer Nov 21 '09 at 9:29
Ah, I see it was a competition problem: mathlinks.ro/viewtopic.php?t=308908 –  Jason Dyer Nov 21 '09 at 13:12

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

-
I don't see even how to constuct your sequence $a_i$ meeting my criteria. Can we decide what is the nth decimal digit for $\sqrt 2$ in an uniformly bounded number of steps? –  Manuel Silva Nov 21 '09 at 16:26
Any irrational number will do, some can be "computed" very fast, like 0.01001000100001... –  sdcvvc Nov 21 '09 at 19:39

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

-