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

I was thinking about a CS problem the other day and somehow got on the topic of the order type of the set of all (finite) binary strings ordered lexicographically. I found that I wasn't able to determine what ordinal number corresponds to the ordering of this set. Does this ordinal have a nice closed-form/name? If so, what is it?

Thanks!

-
I'm not 100% clear on what order you are considering. Usually, the finite binary strings are ordered by first comparing length and then comparing lexicographically. But are you considering $1$ to be greater than all strings that starts with $0$? I.e., compare digits until there is a difference, and if no difference then the string that is an initial segment goes first? –  Arturo Magidin Aug 19 '11 at 16:42
Look at $01$, $001$, $0001$, and so on. This is an infinite descending chain. So the lexicographic ordering is not a well-ordering. But all ordinals are well-ordered. –  André Nicolas Aug 19 '11 at 16:46

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.

-
Thanks for the answer! I was indeed thinking of (2), and I guess that explains why I couldn't find an ordinal for it. :-) –  templatetypedef Aug 19 '11 at 18:56
"Lexicographic order" is a term of art that in my experience always means #2 and never anything else. Computer science jargon for #1 is "shortlex order". That is, compare shortness first, and use lexicographic order to break ties. –  MJD May 30 '12 at 15:34
@Mark: I may be somewhat misguided by the fact that my most common use of "lexicographic order" is that of the basic commutators in groups; they are ordered more or less as in (1) (but with weight replacing length). Thanks for the pointer and clarification. –  Arturo Magidin May 30 '12 at 15:53

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.

-

Aubrey, your explanation looks right, but shouldn't the the order type be called $\omega + \omega\times\mathbb{Q}$? That is the standard notation for the order I think you are describing (the order you get by starting with $\mathbb{Q}$, adding a smallest element, and then replacing each element of the result with a copy of $\omega$).

-
Wouldn't $\omega\times\mathbb{Q}$ be $\omega$ copies of $\mathbb{Q}$ laid 'end-to-end'? The exercise here is effectively $\mathbb{Q}$ copies of $\omega$, so Aubrey's expression looks right to me... –  Steven Stadnicki Sep 30 '11 at 15:20
This is the sort of thing I always mix up, but I was basing my comment on Jech's definition of ordinal multiplication, where the induction clause is $\alpha(\beta+1) = \alpha\beta + \alpha$. Also, Wikipedia describes the order type of a countable non-standard model of arithmetic as $\omega + (\omega^*+\omega)\cdot\eta$, which agrees with the convention Jech lays down for ordinals. –  Marian Sep 30 '11 at 21:15
I mix this up all the time as well, so I did a little digging and it looks like you (Marian) are right. I edited my answer accordingly. –  Aubrey da Cunha Oct 24 '11 at 20:22