# 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$.

## 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. 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 $1$s 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