Talk:Lexicographic order

Untitled

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 $\Sigma =\{a,b\}$ and are ordering strings of $\Sigma ^{*}$.) 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 $\Sigma ^{*}$ called length-plus-lexicographic order. If w₁ = x₁x₂...x_i and w₂ = y₁y₂...y_j then w₁ < w₂ iff i<j or i=j and w₁ << w₂ where << is the lexicographical order on $\Sigma ^{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)

Sipser's Introduction to the Theory of Computation says, "The lexicographic ordering of strings is the same as the familiar dictionary ordering, except that shorter strings precede longer strings. Thus the lexicographic ordering of all strings over the alphabet {0,1} is {empty,0,1,00,01,10,11,000,...}." That would seem to be the Shortlex order ordering. Maybe something should be said noting that the definition is not universal. Steve Checkoway (talk) 23:22, 8 July 2008 (UTC)

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)

Accessible intro

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)

Second the motion... think of me as an intelligent but uninformed reader. As it stands now it says: "Given two partially ordered sets A and B, the lexicographical order on the Cartesian product A × B is defined as (a,b) ≤ (a′,b′) if and only if a < a′ or (a = a′ and b ≤ b′)." I feel like a bunch of knives are being tossed at me to catch. A, B, got 'em. Now here's a and b, what are lower case a,b? part of sets A or B or something else? a and b are not defined! And what is the significance of A and B being partially ordered? Does this whole thing fall apart if they are mostly ordered, or completely unordered, or what? And what on earth is this about a Cartesian product? What does multiplication have to do with putting a series in order, and how can two sets be multiplied, partially ordered or otherwise? Numerous puzzles here, all of which require research before I can solve them, and only then can I learn what I came here to learn. I suggest that if you can't express it clearly you might just not understand it yourself.Friendly Person (talk) 20:54, 3 May 2011 (UTC)

I have split off ==Definition==.--Patrick (talk) 22:11, 3 May 2011 (UTC)

Representability

A word about lexicographical orders being nonrepresentable by real functions in general? —Preceding unsigned comment added by 202.36.179.66 (talk) 02:56, 28 August 2009 (UTC)

Merge Colexicographical order to Lexicographical order

Colexicographical order should be merged into Lexicographical order. I don't think Colexicographical order can ever be more than a dictionary definition; anything of encyclopedic value that can be said in one article can also be said in the other.

The "Definition" section would be a good place to introduce the term. More material could be put in the "Reverse lexicographic order" section if necessary. Melchoir (talk) 02:03, 18 May 2011 (UTC)

Compare with Orderings at OEIS-Wiki

At the moment this article states that reverse lex. order is that of a rhyming dictionary. But Orderings at OEIS-Wiki states that reverse lex. order is lex. order upside down. Reading the OEIS article I would say that colexicographical order is that of a rhyming dictionary. Lipedia (talk) 15:10, 1 January 2012 (UTC)

Image Label Accuracy

On the left side the smaller numbers are have a dark background, on the right side the bigger numbers.

Are the image labels accurate? The 2 labels above the very left grids of red and white squares seem backwards. The labels above the circled numbers all make sense, and on the right side of the image, the labels for the red and white squares match the labels above the circled numbers, but on the left they're switched --Yoda of Borg (talk) 19:16, 5 July 2012 (UTC)

Yes, it looks like there's something wrong. On the right-hand side as well, according to my understanding. The various instances of the word "Rev" seem to be misplaced. Nothing we can immediately do, since the image is not editable, but unless someone can enlighten us as to its correctness, I think it ought to be removed. Victor Yus (talk) 07:26, 6 July 2012 (UTC)

I made it like that for a purpose. You can see that the colors in the arrangements of 20x3 balls on the left and on the right are horizontally reflected, although the numbers are not. So we can see how colex order is related to lex order. The similarity between lex and colex order is not easily shown, and this is one way to do it. However: The actual information are the white numbers. The bluish colors are just a background to make the pattern comprehensible. Lipedia (talk) 09:30, 6 July 2012 (UTC)

But why does it say "Rev Lex" above the top left chart, and "Lex" above the bottom left one? Shouldn't these be the other way round? Victor Yus (talk) 11:01, 6 July 2012 (UTC)

Left side:
When the actual triples (caption in gray) are in lex order, the corresponding binary vectors (red caption) are in revlex order.
Right side:
When the actual triples are in colex order, the corresponding binary vectors are in are in colex order as well.
Compare:
v:Lexicographic and colexicographic order#Permutations - When permutations are in revcolex order the corresponding inversion vectors are in colex order.
Lipedia (talk) 12:29, 6 July 2012 (UTC)

OK, I see, I guess it's correct. But for this to make any sense, it all needs to be explained in the article. There seems to be nothing in the article about binary vectors, or how they might "correspond" to subsets (and in fact I don't think it's strictly subsets that are being ordered here, but ordered triples). I also agree with the proposal to merge the article on colex order with this one. And there seems to be inconsistency in the definition of reverse lex order as given in the article and as used here. Lots to sort out. Victor Yus (talk) 10:15, 7 July 2012 (UTC)

I think the red ordering (binary vectors) is correct or incorrect whether we consider that the most significant bit is on the left or right. If we consider that the least significant bit is on the left, then the red and the blue ordering should be the same. Can someone confirm or infirm ? If so, it might be worse detailing this in the legend ? Tartolamp (talk) 15:42, 5 April 2018 (UTC)

Misleading comma/phrasing

The article says (paraphrased) the word A comes before B "if and only if the first a_i, which is different from b_i, comes before b_i in the alphabet.

This could be misinterpreted as implying a_1!=b_1 due to the comma appearing before "which," when the intention was clearly to define i to be the least i such that a_i!=b_i. It seems like bad practice to place the definition of a variable inside what one might interpret as an appositive phrase, though with that interpretation i would be appearing without any definition whatsoever. Jaycob Coleman (talk) 01:37, 26 November 2013 (UTC)

I attempted to clarify it. -- Elphion (talk) 04:02, 26 November 2013 (UTC)

like your article

I'm taking classes again and need a quick reference to the word. Found extensive discussion that was so much more useful and enlightening on the subject. Now I can go back to class with a much better understanding of, and ability within the subject area. Thank you MGMontini (talk) 17:29, 22 October 2015 (UTC) MGMontini (talk) 17:29, 22 October 2015 (UTC)

Rewriting this article is needed

As it is, the article is highly confusing and misleading. The main point is that the lexicographical order is primarily defined for sequences (word over an alphabet) and that this case is not even described. Moreover the other variants of the lexicographical order may easily be described by reducing them to the case of sequences, and this gives a description which is much easier to understand (except, maybe, for specialists of abstract set theory) than that which is presently given.

I'll try to fixing this mess. D.Lazard (talk) 10:27, 18 June 2016 (UTC)

I have started cleaning up this article. I have a problem with the recent additions by Frobitz, because of their numerous issues:

• There are copyright violations, as being verbatim copies of sentences and examples of the cited web site. Without the other issues, this would be easy to solve by rewriting the sentences and changing the examples.
• The source of these additions are a wiki. Thus this is not a reliable source.
• They use the terms internal order and external order which are not defined in Wikipedia nor in the source. These have not any evident meaning as there are more than two orders that are involved here (the order being defined, the order used to convert subsets into sequences, the order for reading the sequences, the order for comparing elements, and the display order).
• The name used for these ordering do not seem to be standard.

I'll thus remove these additions. D.Lazard (talk) 15:32, 21 June 2016 (UTC)

Possible mistake?

In the last sentence of the "Motivation and definition" section, when it says "of a fixed length", this seems a bit trivial and silly, maybe what it meant to say is "of finite length"? — Preceding unsigned comment added by 89.93.179.93 (talk) 13:23, 13 April 2017 (UTC)

The set of words of finite length, even over a finite alphabet, is not well ordered by the lexicographic order. Consider words over the alphabet {0, 1} (with 0 < 1), and consider the subset S of all words whose last letter is 1. If the lexicographic order were a well-order, S should have a least word w. But for any putative least word w in S, you can change the last letter from 1 to 01, yielding another word in S that precedes w in the lexicographic order. Thus there can be no least element of S. -- Elphion (talk) 13:53, 13 April 2017 (UTC)

This should be mentioned in the article itself, no other source mentions that strings of finite length is not well ordered on lexicographic order, and the statement in the article itself is misleading by itself. 202.36.245.54 (talk) 01:51, 25 March 2018 (UTC)

This is essentially said in section "Cartesian products". However, I agree that this section is too technical, and that it may be unclear for most readers that an element of a Cartesian product is nothing else than a sequence such that the set in which an element lives may depend of the place of the element in the sequence. D.Lazard (talk) 08:52, 25 March 2018 (UTC)

Lexicographic ordering in multi-objective optimization

There is a need of defining Lexicographic ordering in the context of multi-objective optimization. — Preceding unsigned comment added by Qx2020 (talk • contribs) 09:45, 21 June 2017 (UTC)

Motivation and definition section

I have largely rewritten the section "Motivation and definition" in response to the "clarify" tag placed there in March, 2020. Hope it helps. -- Elphion (talk) 18:55, 19 June 2020 (UTC)

I'm removing the clarify tag, because it seems it's now been clarified. 67.198.37.16 (talk) 06:14, 16 October 2020 (UTC)

Explanation is terrible

This is a terribly confusing set of explanations of a relatively simple idea. Mathematicians are increasingly using terminology and notation that are more complex than the ideas they are trying to describe. Mathematics is becoming swamped with people more concerned with definitions and notation than Mathematics. As a professional Mathematician of many years this brings me close to tears. I think Wikipedia can do better. — Preceding unsigned comment added by 216.36.134.73 (talk)

The current text in "Definition and Motivation" replaced a significantly more abstruse version. If you have suggestions for improvement, please add them below. And please sign your comments by appending four tildes (~~~~) at the end. -- Elphion (talk) 08:50, 23 September 2020 (UTC)

Parsing error

I corrected a parsing error, and this is the result: $$a_{1}+\cdots +a_{n}=b_{1}+\cdots +b_{n}\quad {\text{ and }}\quad a_{i}>b_{i}{\text{ for the largest }}i{\text{ for which }}a_{i}\neq b_{i}.$$. TMM53 (talk) 04:15, 16 February 2023 (UTC)