5
$\begingroup$

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 <= 01).

For a finite set this is easy: arrange the set in order and assign an increasing sequence of binary sequences.

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

For the rationals this is already a bit more difficult. I believe the following works: Take the Stern-Brocot tree. 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.

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.

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

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.

Since you have a solution for $\mathbb Q$, for other sets just compose the order preserving injection from above with this solution.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ You can skip the rationals entirely, and prove directly that there's a mapping to the binary sequences. You just have to enumerate the set and map each element to a value between the images of the neighbouring values among those you've already mapped. You only have to take care never to map anything to 0. $\endgroup$
    – Zsbán Ambrus
    Commented Mar 20, 2011 at 10:47

You must log in to answer this question.

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