2
$\begingroup$

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.

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

2 Answers 2

4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Nov 21, 2009 at 16:26
  • 1
    $\begingroup$ Any irrational number will do, some can be "computed" very fast, like 0.01001000100001... $\endgroup$
    – sdcvvc
    Nov 21, 2009 at 19:39
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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