increasing bijection - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T11:17:00Z http://mathoverflow.net/feeds/question/6337 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/6337/increasing-bijection increasing bijection Manuel Silva 2009-11-21T00:47:10Z 2009-11-21T21:07:03Z <p>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.</p> <p><a href="http://en.wikipedia.org/wiki/Back-and-forth_method" rel="nofollow">http://en.wikipedia.org/wiki/Back-and-forth_method</a></p> <p>I would like to have a "natural" bijection. The algorithm resulting from the back-and-forth method behaves rather chaotically. </p> <p>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.</p> http://mathoverflow.net/questions/6337/increasing-bijection/6341#6341 Answer by Foo for increasing bijection Foo 2009-11-21T01:47:53Z 2009-11-21T01:47:53Z <p>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$. </p> http://mathoverflow.net/questions/6337/increasing-bijection/6404#6404 Answer by sdcvvc for increasing bijection sdcvvc 2009-11-21T20:55:23Z 2009-11-21T21:07:03Z <p>The Stern-Brocot tree gives a representation of (Q<sup>+</sup>,&lt;) 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,&lt;) 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,&lt;) and sum of two trees corresponding to (Q-{0},&lt;).</p> <p>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:</p> <pre><code> root(T1) merge(T1,T2) = / \ left(T1) root(T2) / \ merge(right(T1),left(T2)) right(T2) </code></pre> <p>(to be precise, this definition is <a href="http://mathoverflow.net/questions/740/co-induction-understanding" rel="nofollow">coinductive</a>)</p> <p>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.]</p>