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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Do you mean "naturals without zero"? I haven't seen any mention of the exact bijection you mention. $\endgroup$
    – Jason Dyer
    Commented 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$
    – Jonas Meyer
    Commented Nov 21, 2009 at 9:29
  • $\begingroup$ Ah, I see it was a competition problem: mathlinks.ro/viewtopic.php?t=308908 $\endgroup$
    – Jason Dyer
    Commented Nov 21, 2009 at 13:12

2 Answers 2

Reset to default
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$.

Improve this answer
$\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$
    – Manuel Silva
    Commented Nov 21, 2009 at 16:26
  • 1
    $\begingroup$ Any irrational number will do, some can be "computed" very fast, like 0.01001000100001... $\endgroup$
    – sdcvvc
    Commented 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.]

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .