Mapping rationals to strings

Show that there is an injective order-preserving map from \mathbb{Q} to the set of finite strings \{0,1\}^* with the lexicographical order.

The lexicographical order is defined as follows: \alpha < \beta holds if and only if any of the two following conditions hold.

  1. The string \alpha is a proper prefix of \beta, i.e. \beta = \alpha\gamma for some nonempty string \gamma \in \{0,1\}^*.
  2. The strings are of the forms \alpha = \gamma 0 \delta and \beta = \gamma 1 \sigma, for arbitrary strings \gamma,\delta,\sigma \in \{0,1\}^*.

For instance, 0 < 00 < 01 < 010 < 011 < 1 < 10.


Mapping rationals to strings

3 thoughts on “Mapping rationals to strings

  1. To prove this let us prove a pretty general lemma first. Consider infinitely countable, total ordered sets, with no maximum or minimum, and such that for every two elements x < y there exists a z such that x < z < y.

    Lemma: Up to ismorphism there is only one set with this characteristics and this is in fact the set of rational numbers with its usual order.
    Proof: Call two such sets X and Y and let x_n and y_n count the elements of X and Y repectively. We define an order preserving bijection by induction on n. At each step we will say where the bijection maps x_0 ... x_n and where the inverse of the bijection maps y_0 ... y_n.
    Base case: Take x_0 and send it to y_0.
    Inductive case: Now assume one has the bijection (and its inverse) defined on x_0 ... x_n and y_0 ... y_n. Suppose that x_i goes to y'_i and y_i to x'_i. Take x_{n+1}, if you already mapped a y_i with i < n+1 to it, you are done. Else see what is his order with respect to x_0 ... x_n. Suppose that the order goes: ... < x_i < x_{n+1} < x_j < ... . Then just send x_{n+1} to an element y \in Y such that y'_i < y < y'_j and y is different from all the others y_i, i<n+1. This element exists by hypothesis. It might be the case that x_{n+1} is the maximum or the minimum of the x_0 ... x_{n+1}. This is not a problem since the fact that Y has no maximum or minimum tells us that we will always have a new y with the correct relative order to choose. Now make exactly the same reasoning but with y_{n+1}.
    This concludes the inductive step.
    Notice that the constructed function is indeed a bijection since we didn't leave out any x or y.

    With this lemma we are almost done. Notice that if we take all the strings that end in 0 out of {0,1}* we get an ordered set in the hypothesis of the lemma. This is not obvious, it is easy to see that there is no maximum and no minumum, but one has to consider some cases to see that for every pair of distinct elements there exists another element in between. Suppose we are given x < y. We consider two cases: either x is a prefix of y or it isn't. In the first case take z to be x concatenated with $0…01$. Where we put enough 0's such that z is longer than y. In the second case x and y differ in a coordinate i and thus x has a 0 in the coordinate i and y has a 1. Take z to be x concatenated with just a 1.

    Liked by 2 people

  2. fmartin says:

    Two minor observations:

    1) The order topology in \{0,1\}^* is the metric topology induced by the ultrametric d(x,y) = 2^{-n}, where n is the smallest index in which x and y differ. This popped up when I tried to think about the problem topologically.

    2) Luis’ argument actually characterizes the structure of \{0,1\}^*; it is order isomorphic to \mathbb{N}+(\mathbb{Q}\times \mathbb{N}). Let X denote the set of finite binary strings ending in 1 and let f:\mathbb{Q}\to X be an order isomorphism. If Y denotes the set of finite binary strings containing at least one 1, then we may produce an order isomorphism g:\mathbb{Q}\times\mathbb{N}\to Y by setting g(x,n) as the concatenation of f(x) and n zeroes. Since the set of strings not containing any 1s is order isomorphic to \mathbb{N} and each of them is smaller than any element in Y, the result follows.

    Liked by 2 people

  3. This is the original proof I had in mind; it works for any countable set X having a total order.

    Consider an enumeration x_0, x_1, \hdots of the elements of X. Let f : X \to \{0,1\}^* be the map defined by f(x_n) = a_1 \hdots a_n, where a_i = 1 if x_i \leq x_n and a_i = 0 otherwise.

    Note that f is injective since f(x_n) is a string of length n. To see that f is order-preserving, let x_n < x_m, consider their images f(x_n) = a_1 \hdots a_n and f(x_m) = b_1 \hdots b_m, and let us show that a_1 \hdots a_n < b_1 \hdots b_m.

    Observe that a_i \leq b_i for all 1 \leq i \leq \min\{n,m\}. Indeed, if x_i \leq x_n then a_i = 1 and b_i = 1 since x_i \leq x_n < x_m. On the other hand, if x_i > x_n then a_i = 0 and trivially a_i \leq b_i.

    To conclude the proof we consider two cases:

    1. If n < m, then a_i \leq b_i for all 1 \leq i \leq n. Hence a_1 \hdots a_n \leq b_1 \hdots b_n < b_1 \hdots b_n b_{n+1} \hdots b_m.

    2. If n > m, then a_i \leq b_i for all 1 \leq i \leq m. Moreover, a_m = 0, since it is not the case that x_m \leq x_n, but b_m = 1, since it is the case that x_m \leq x_m. Hence a_1 \hdots a_{m-1} a_m a_{m+1} \hdots a_n = a_1 \hdots a_{m-1} 0 a_{m+1} \hdots a_n \leq b_1 \hdots b_{m-1} 0 a_{m+1} \hdots a_n < b_1 \hdots b_{m-1} 1 = b_1 \hdots b_{m-1} b_m, as required.

    (Simple lemma we used: if a_i \leq b_i for all 1 \leq i \leq n then a_1 \hdots a_n \leq b_1 \hdots b_n).

    Liked by 2 people

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s