3 edited tags
2 added 39 characters in body; edited tags

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

1

# Injections to binary sequences that preserve order

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.