Talk:Lexicographical order

From Wikipedia, the free encyclopedia

The term "dictionary order" is a misnomer: most dictionaries are not in simple lexicographical order. -- The Anome 08:18, 10 Apr 2004 (UTC)

Nevertheless, "dictionary order" is standard mathematical terminology, regardless of whether it completely conforms to the ordinary use of the term. BTW, I see no reason why the number of sets cannot be generalised to range over any ordinal number, (e.g. here it is given for a finite ordinal, but the definition for countable number seems obvious, and the definition for an arbitrary ordinal seems like it should make sense.) Revolver 23:34, 7 Jul 2004 (UTC)

An important property of the lexicographical order is that it preserves well-orders, that is, if A and B are well-ordered sets, then the product set A × B with the lexicographical order is also well-ordered.

Isn't this just ordinal multiplication, with the order of A and B reversed? If this is the case, is it possible to define ordinal multiplication where the factors themselves are indexed by an ordinal? I've seen cardinal multiplication defined for indexed families, but not ordinal. Revolver 23:46, 7 Jul 2004 (UTC)
Ah, I think I see where I screwing up. It is true (I checked a set theory book) that the product of two ordinals is the dictionary ordering on the cartesian product, with the order of factors reversed. And, it also seems true (I haven't gone through the details) that if you have a family of totally ordered sets, indexed by an ordinal number, then you could define the dictionary ordering on that family, and it would again turn out to be a totally ordered set. (Define: if two elements aren't equal, then they disagree in a coordinate, these coordinates are indexed by an ordinal, so the set of all coordinates where they disagree is a nonempty set, has a least element, compare at that coordinate.) In particular, you could do this for a family of well-ordered sets, but in this case, the dictionary order might not be well-ordered. (Consider the dictionary order on 2, 2, 2, 2, ..., where the index ordinal is w. Then 1, 1, 1, 1, 1, ...; 1, 0, 1, 1, 1 ; ..., 1, 0, 0, 1, 1, ...; etc. is a strictly decreasing sequence in 2, 2, 2, ..., so it can't be well-ordered.) Revolver 01:10, 8 Jul 2004 (UTC)


There is a problem here with how the ordering is extended to products of different lengths. (For simplicity I'll assume we have a fixed alphabet Σ = {a,b} and are ordering strings of Σ * .) The standard dictionary order is what (Sims 94, Computation With Finitely Presented Groups) calls the left-right-lexicographic order. This is not a well-order, since if a < b then b > ab > aab > aaab > ... is an infinite decreasing sequence of elements. In general strings of fixed length do preserver the well-ordering property but by using the 'space padding' method described in the article to extend the definition to the LR-lex order the property no longer holds.

There, is, however, a natural ordering on Σ * called length-plus-lexicographic order. If w1 = x1x2...xi and w2 = y1y2...yj then w1 < w2 iff i<j or i=j and w1 << w2 where << is the lexicographical order on Σk. To see how these orders differ, consider the following examples.

Set: {b,ab,aab,aaab,...}

  • Left-right-lexicographic ordering: b > ab > aab > aaab > ...
  • Length-plus-lexicographic ordering: b < ab < aab < aaab < ...

Set: {a,b,aa,bb,abab}

  • Left-right-lexicographic ordering: a < aa < abab < b < bb
  • Length-plus-lexicographic ordering: a < b < aa < bb < abab

There is also a wreath product of orderings on sets that preserves the well-ordering property but it is a bit involved to explain here. Maybe at some point in the future I'll take a shot at rewriting this page to include these definitions. TooMuchMath 22:14, 26 April 2006 (UTC)

That would be nice. Another observation is that these are all equivalent for any set with the prefix property. Calbaer 22:51, 6 November 2006 (UTC)
I added a paragraph on the ordering of strings, in which I also mention what you call Length-plus-lexicographic ordering; I found a stub (Shortlex order) which describes it. Let us expand it! I'll start by adding the alternate names Length-plus-lexicographic and Radix order - that's the name I knew for it. --fudo (questions?) 20:19, 25 February 2007 (UTC)

[edit] Removed C++ string comparison

Why did we have a C++ string comparison function here? It is, at most, marginally related to the topic of this article. Moreover, why case insensitive? Lexicographic orders have nothing to do (are ortogonal) to being case (in)sensitive. Since, anyway, Wikipedia is not a collection of "how-to"s, I've decided to remove this section. --NavarroJ 11:21, 16 September 2006 (UTC)

[edit] Accessible intro

This article may be too technical for a general audience.
Please help improve this article by providing more context and better explanations of technical details to make it more accessible, without removing technical details.

There should be a more accessible introduction, which gives an example that older elementary school children (and for that matter high school students and non-mathematically inclined adults) can understand. -- Beland 06:21, 23 September 2007 (UTC)