What is the ordinal number for the set of binary strings ordered lexicographically?

Consider the set of all (finite) binary strings $\{0,1\}^*$ ordered lexicographically. What ordinal number corresponds to the ordering of this set? Does this ordinal have a nice closed-form/name? If so, what is it?

Solution 1:

Following Arturo's interpretation (2), you can still get a handle on the order type. Specifically, it is $\omega+\mathbb{Q}\times \omega$. The first $\omega$ is the strings consisting of all 0's. Any string containing at least one 1 can be considered the binary expansion of a dyadic rational in $(0,1)$ ending in 1 followed by some number of 0's. The dyadic rationals in $(0,1)$ are order-isomorphic to $\mathbb{Q}$ by the usual ordering (which agrees with the lexicographic ordering after you trim the trailing 0's). The number of trailing 0's gives you the remaining factor of $\omega$.

Arturo's example gives an infinite decreasing sequence in the "$\mathbb{Q}$" part, so you won't get an ordinal order type, but the rationals are considered one of the "basic" order types, so it's not so bad.

EDIT: As Marian points out, the math is right, but the typography is wrong. It is, in fact, $\omega+\omega\times\mathbb{Q}$. See i.e. http://en.wikipedia.org/wiki/Ordinal_multiplication, which in turn cites Jech.

Solution 2:

I can think of two plausible interpretations of "ordered lexicographically".

1. My first read was that you order the strings by first comparing length, letting the shortest string be smaller; and if the two strings have the same length, then you compare them digit by digit until you get the first difference. The string with a $0$ at the different position is smaller.

   With this ordering, you simply get $\omega$: you have a well-ordered countable set in which every element has only finitely many strictly smaller elements.

   But because this is so easy, it struck me halfway through thinking about it that it probably is not what you meant, leading to the following other interpretation:

2. Start comparing digits of the strings. If you find a difference before the smaller string "terminates", then the string with a $0$ in the first difference is the smaller one. If one of the strings is a proper initial segment of the other, then the proper initial segment is the smaller one.

   But this set is not well-ordered. Consider the collection of all finite sequences that are a string of $0$s followed by a single $1$. Then $1\gt 01 \gt 001 \gt 0001 \gt 00001 \gt 000001 \gt\cdots$ is an infinite descending sequence.

   So this ordering does not have an ordinal type.