Injections to binary sequences that preserve order - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T03:41:54Z http://mathoverflow.net/feeds/question/58917 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/58917/injections-to-binary-sequences-that-preserve-order Injections to binary sequences that preserve order Jules 2011-03-19T11:54:20Z 2011-03-19T13:30:39Z <p>Suppose we have a countable set S with a total order. Can we give an injection from S to the set of finite binary sequences that end in all zeros that preserves the ordering? The order on binary sequences is the dictionary ordering (e.g. 001001 &lt;= 01).</p> <p>For a finite set this is easy: arrange the set in order and assign an increasing sequence of binary sequences.</p> <p>For the natural numbers this is also easy: send a number n to the sequence that starts with n ones (a similar solution works for negative numbers).</p> <p>For the rationals this is already a bit more difficult. I believe the following works: Take the <a href="http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree" rel="nofollow">Stern-Brocot tree</a>. Start at the root and walk down to the rational number. Every time you go left, write a 0. Every time you go right, write a 1. Finally write another 1.</p> <p>So an equivalent formulation seems to be: can we arrange S into a binary tree such that the elements are arranged in order from left to right as in the Stern-Brocot tree.</p> <p>My question is: can this be done for any countable set with a total order? The question came up in a discussion whether radix sort can be used to sort any set (radix sort can sort binary sequences).</p> http://mathoverflow.net/questions/58917/injections-to-binary-sequences-that-preserve-order/58919#58919 Answer by Gjergji Zaimi for Injections to binary sequences that preserve order Gjergji Zaimi 2011-03-19T13:10:01Z 2011-03-19T13:10:01Z <p>It is easy to prove that for any countable linearly ordered set there is an order preserving injection to the rationals. This can be proven by enumerating the base set and then specifying the values of the mapping by induction. </p> <p>Since you have a solution for \$\mathbb Q\$, for other sets just compose the order preserving injection from above with this solution.</p>