Show that there is an injective order-preserving map from to the set of finite strings with the lexicographical order.

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

- The string is a proper prefix of , i.e. for some nonempty string .
- The strings are of the forms and , for arbitrary strings .

For instance, .

Advertisements

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 there exists a such that .

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 and and let and count the elements of and repectively. We define an order preserving bijection by induction on . At each step we will say where the bijection maps and where the inverse of the bijection maps .

Base case: Take and send it to .

Inductive case: Now assume one has the bijection (and its inverse) defined on and . Suppose that goes to and to . Take , if you already mapped a with to it, you are done. Else see what is his order with respect to . Suppose that the order goes: . Then just send to an element such that and is different from all the others , . This element exists by hypothesis. It might be the case that is the maximum or the minimum of the . This is not a problem since the fact that 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 .

This concludes the inductive step.

Notice that the constructed function is indeed a bijection since we didn't leave out any or .

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 . We consider two cases: either is a prefix of or it isn't. In the first case take to be concatenated with $0…01$. Where we put enough 0's such that is longer than . In the second case and differ in a coordinate and thus has a in the coordinate and has a . Take to be concatenated with just a .

LikeLiked by 2 people

Two minor observations:

1) The order topology in is the metric topology induced by the ultrametric , where is the smallest index in which and differ. This popped up when I tried to think about the problem topologically.

2) Luis’ argument actually characterizes the structure of ; it is order isomorphic to . Let denote the set of finite binary strings ending in and let be an order isomorphism. If denotes the set of finite binary strings containing at least one , then we may produce an order isomorphism by setting as the concatenation of and zeroes. Since the set of strings not containing any s is order isomorphic to and each of them is smaller than any element in , the result follows.

LikeLiked by 2 people

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

Consider an enumeration of the elements of . Let be the map defined by , where if and otherwise.

Note that is injective since is a string of length . To see that is order-preserving, let , consider their images and , and let us show that .

Observe that for all . Indeed, if then and since . On the other hand, if then and trivially .

To conclude the proof we consider two cases:

1. If , then for all . Hence .

2. If , then for all . Moreover, , since it is not the case that , but , since it is the case that . Hence , as required.

(Simple lemma we used: if for all then ).

LikeLiked by 2 people