Editing Lexicographic order

{{short description|Generalization of the alphabetical order of dictionaries to sequences of elements of an ordered set}}
{{more citations needed|date=January 2022}}
{{Hatnote|For similarly named ordering systems outside mathematics, see [[alphabetical order]], [[natural sort order]], [[lexicographic preferences]], and [[collation]].}}

In [[mathematics]], the '''lexicographic''' or '''lexicographical order''' (also known as '''lexical order''', or '''dictionary order''') is a generalization of the [[alphabetical order]] of the [[dictionaries]] to [[sequence]]s of ordered symbols or, more generally, of elements of a [[totally ordered set]].

There are several variants and generalizations of the lexicographical ordering. One variant applies to sequences of different lengths by comparing the lengths of the sequences before considering their elements.

Another variant, widely used in [[combinatorics]], orders [[subset]]s of a given [[finite set]] by assigning a total order to the finite set, and converting subsets into [[Sequence#Increasing_and_decreasing|increasing sequences]], to which the lexicographical order is applied. 

A generalization defines an order on an ''n''-ary [[Cartesian product]] of [[partially ordered set]]s; this order is a total order if and only if all factors of the Cartesian product are totally ordered.

==Definition==

The words in a [[lexicon]] (the set of words used in some language) have a conventional ordering, used in [[dictionaries]] and [[encyclopedias]], that depends on the underlying ordering of the alphabet of symbols used to build the words. The lexicographical order is one way of formalizing word order given the order of the underlying symbols.

The formal notion starts with a [[finite set]] {{math|''A''}}, often called the [[alphabet (formal languages)|alphabet]], which is [[totally ordered]]. That is, for any two symbols {{math|''a''}} and {{math|''b''}} in {{math|''A''}} that are not the same symbol, either {{math|''a'' < ''b''}} or {{math|''b'' < ''a''}}.

The ''words'' of {{math|''A''}} are the finite sequences of symbols from {{math|''A''}}, including words of length 1 containing a single symbol, words of length 2 with 2 symbols, and so on, even including the empty sequence <math>\varepsilon</math> with no symbols at all. The lexicographical order on the set of all these finite words orders the words as follows:

# Given two different words of the same length, say {{math|''a'' {{=}} ''a''<sub>1</sub>''a''<sub>2</sub>...''a''<sub>''k''</sub>}} and {{math|''b'' {{=}} ''b''<sub>1</sub>''b''<sub>2</sub>...''b''<sub>''k''</sub>}}, the order of the two words depends on the alphabetic order of the symbols in the first place {{math|''i''}} where the two words differ (counting from the beginning of the words):  {{math|''a'' < ''b''}} if and only if {{math|''a''<sub>''i''</sub> < ''b''<sub>''i''</sub>}} in the underlying order of the alphabet {{math|''A''}}.
# If two words have different lengths, the usual lexicographical order pads the shorter one with "blanks" (a special symbol that is treated as smaller than every element of {{math|''A''}}) at the end until the words are the same length, and then the words are compared as in the previous case.

However, in [[combinatorics]], another convention is frequently used for the second case, whereby a shorter sequence is always smaller than a longer sequence. This variant of the lexicographical order is sometimes called {{em|[[shortlex order]]}}.

In lexicographical order, the word "Thomas" appears before "Thompson" because they first differ at the fifth letter ('a' and 'p'), and letter 'a' comes before the letter 'p' in the alphabet. Because it is the first difference, in this case the 5th letter is the "most significant difference" for alphabetical ordering.

An important property of the lexicographical order is that for each {{math|''n''}}, the set of words of length {{math|''n''}} is [[well-order]]ed by the lexicographical order (provided the alphabet is finite); that is, every decreasing sequence of words of length {{math|''n''}} is finite (or equivalently, every non-empty subset has a least element).<ref name="Harzheim"/><ref name="BaaderNipkow1999">{{cite book|author1=Franz Baader|author2=Tobias Nipkow|title=Term Rewriting and All That|year=1999|publisher=Cambridge University Press|isbn=978-0-521-77920-3|pages=18–19}}</ref> It is not true that the set of ''all'' finite words is well-ordered; for example, the infinite set of words {b, ab, aab, aaab, ... } has no lexicographically earliest element.

==Numeral systems and dates==

The lexicographical order is used not only in dictionaries, but also commonly for numbers and dates.

One of the drawbacks of the [[Roman numeral system]] is that it is not always immediately obvious which of two numbers is the smaller. On the other hand, with the [[positional notation]] of the [[Hindu–Arabic numeral system]], comparing numbers is easy, because the natural order on [[natural number]]s is the same as the variant [[shortlex order|shortlex]] of the lexicographic order. In fact, with positional notation, a natural number is represented by a sequence of [[numerical digit]]s, and a natural number is larger than another one if either it has more digits (ignoring leading zeroes) or the number of digits is the same and the first (most significant) digit which differs is larger.

For [[real number]]s written in [[decimal notation]], a slightly different variant of the lexicographical order is used: the parts on the left of the decimal point are compared as before; if they are equal, the parts at the right of the decimal point are compared with the lexicographical order. The padding 'blank' in this context is a trailing "0" digit.

When negative numbers are also considered, one has to reverse the order for comparing negative numbers. This is not usually a problem for humans, but it may be for [[computer]]s (testing the sign takes some time). This is one of the reasons for adopting [[two's complement]] representation for representing [[signed integer]]s in computers.

Another example of a non-dictionary use of lexicographical ordering appears in the [[ISO 8601]] standard for dates, which expresses a date as YYYY-MM-DD. This formatting scheme has the advantage that the lexicographical order on sequences of characters that represent dates coincides with the [[chronological order]]: an earlier CE date is smaller in the lexicographical order than a later date up to year 9999. This date ordering makes [[sorting algorithm|computerized sorting]] of dates easier by avoiding the need for a separate sorting algorithm.

==Monoid of words==

The {{em|monoid of words}} over an alphabet {{math|''A''}} is the [[free monoid]] over {{math|''A''}}. That is, the elements of the monoid are the finite sequences (words) of elements of {{math|''A''}} (including the empty sequence, of length 0), and the operation (multiplication) is the [[concatenation]] of words. A word {{math|''u''}} is a [[prefix (computer science)|prefix]] (or 'truncation') of another word {{math|''v''}} if there exists a word {{math|''w''}} such that {{math|1=''v'' = ''uw''}}. By this definition, the empty word (<math>\varepsilon</math>) is a prefix of every word, and every word is a prefix of itself (with {{math|''w''}} <math> = \varepsilon</math>); care must be taken if these cases are to be excluded.

With this terminology, the above definition of the lexicographical order becomes more concise: Given a [[Partial order|partially]] or [[total order|totally ordered]] set {{math|''A''}}, and two words {{math|''a''}} and {{math|''b''}} over {{math|''A''}} such that {{math|''b''}} is non-empty, then one has {{math|''a'' < ''b''}} under lexicographical order, if at least one of the following conditions is satisfied:

* {{math|''a''}} is a prefix of {{math|''b''}}
* there exists words {{math|''u''}}, {{math|''v''}}, {{math|''w''}} (possibly empty) and elements {{math|''x''}} and {{math|''y''}} of {{math|''A''}} such that
::{{math|''x'' < ''y''}}
::{{math|1=''a'' = ''uxv''}}
::{{math|1=''b'' = ''uyw''}}

Notice that, due to the prefix condition in this definition, <math>\varepsilon < b\,\, \text{ for all } b \neq \varepsilon,</math> where <math>\varepsilon</math> is the empty word.

If <math>\,<\,</math> is a total order on <math>A,</math> then so is the lexicographic order on the words of <math>A.</math> However, in general this is not a [[well-order]], even if the alphabet <math>A</math> is well-ordered. For instance, if {{math|1=''A'' = {''a'', ''b''}{{void}}}}, the [[Formal language|language]] {{math|{''a''<sup>''n''</sup>''b'' {{!}} ''n'' ≥ 0, ''b'' > ''ε''}{{void}}}} has no least element in the lexicographical order: {{math|... < ''aab'' < ''ab'' < ''b''}}.

Since many applications require well orders, a variant of the lexicographical orders is often used. This well-order, sometimes called {{em|[[shortlex]]}} or {{em|quasi-lexicographical order}}, consists in considering first the lengths of the words (if {{math|length(''a'') < length(''b'')}}, then <math>a < b</math>), and, if the lengths are equal, using the lexicographical order. If the order on {{math|''A''}} is a well-order, the same is true for the shortlex order.<ref name="BaaderNipkow1999"/><ref>{{cite book | last=Calude | first=Cristian | author-link=Cristian S. Calude | title=Information and randomness. An algorithmic perspective | url=https://archive.org/details/informationrando00calu_163 | url-access=limited | series=[[EATCS]] Monographs on Theoretical Computer Science | publisher=[[Springer-Verlag]] | year=1994 | isbn=3-540-57456-5 | zbl=0922.68073 | page=[https://archive.org/details/informationrando00calu_163/page/n19 1] }}</ref>

==Cartesian products==

The lexicographical order defines an order on an ''n''-ary [[Cartesian product]] of ordered sets, which is a total order when all these sets are themselves totally ordered. An element of a Cartesian product <math>E_1 \times \cdots \times E_n</math> is a sequence whose <math>i</math><sup>th</sup> element belongs to <math>E_i</math> for every <math>i.</math> As evaluating the lexicographical order of sequences compares only elements which have the same rank in the sequences, the lexicographical order extends to Cartesian products of ordered sets.

Specifically, given two [[partially ordered set]]s <math>A</math> and <math>B,</math> the {{visible anchor|lexicographical order on the Cartesian product|Lexicographic order on Cartesian products}} <math>A \times B</math> is defined as
<math display=block>(a, b) \leq \left(a^{\prime}, b^{\prime}\right) \text{ if and only if } a < a^{\prime} \text{ or } \left(a = a^{\prime} \text{ and } b \leq b^{\prime}\right),</math>

The result is a partial order. If <math>A</math> and <math>B</math> are each [[Total order|totally ordered]], then the result is a total order as well. The lexicographical order of two totally ordered sets is thus a [[linear extension]] of their [[product order]].

One can define similarly the lexicographic order on the Cartesian product of an infinite family of ordered sets, if the family is indexed by the [[natural number]]s, or more generally by a well-ordered set. This generalized lexicographical order is a total order if each factor set is totally ordered.

Unlike the finite case, an infinite product of well-orders is not necessarily well-ordered by the lexicographical order. For instance, the set of [[countably infinite]] binary sequences (by definition, the set of functions from natural numbers to <math>\{ 0, 1 \},</math> also known as the [[Cantor space]] <math>\{ 0, 1 \}^{\omega}</math>) is not well-ordered; the subset of sequences that have precisely one <math>1</math> (that is, {{math|{ 100000..., 010000..., 001000..., ... }{{void}}}}) does not have a least element under the lexicographical order induced by <math>0 < 1,</math> because {{math|100000... > 010000... > 001000... > ...}} is an [[infinite descending chain]].<ref name="Harzheim">{{cite book|author=Egbert Harzheim|title=Ordered Sets|year=2006|publisher=Springer|isbn=978-0-387-24222-4|pages=88–89}}</ref> Similarly, the infinite lexicographic product is not [[Noetherian relation|Noetherian]] either because {{math|011111... < 101111... < 110111 ... < ...}} is an infinite ascending chain.

== Functions over a well-ordered set==

The functions from a [[well-ordered set]] <math>X</math> to a [[totally ordered set]] <math>Y</math> may be identified with sequences indexed by <math>X</math> of elements of <math>Y.</math> They can thus be ordered by the lexicographical order, and for two such functions <math>f</math> and <math>g,</math> the lexicographical order is thus determined by their values for the smallest <math>x</math> such that <math>f(x) \neq g(x).</math>

If <math>Y</math> is also well-ordered and <math>X</math> is finite, then the resulting order is a well-order. As shown above, if <math>X</math> is infinite this is not the case.

==Finite subsets==

[[File:Orderings; 6 choose 3.svg|thumb|340px|Orderings of the 3-[[subset]]s of <math>\{1, \ldots, 6\},</math> represented as sets of red squares, increasing sequences (in blue), or by their [[indicator function]]s, converted in [[decimal notation]] (in grey). The grey numbers are also the rank of the subsets in all subsets of <math>\{1, \ldots, 6\},</math> numbered in colexicographical order, and starting from 0. The lexicographical (lex) and colexicographical (colex) orders are on the top and the corresponding reverse orders (rev) on the bottom<br>One passes from an order to its reverse order, either by reading bottom-up instead of up-bottom, or by exchanging red and white colors.]]

In [[combinatorics]], one has often to enumerate, and therefore to order the [[finite subset]]s of a given set <math>S.</math> For this, one usually chooses an order on <math>S.</math> Then, [[sorting]] a subset of <math>S</math> is equivalent to convert it into an increasing sequence. The lexicographic order on the resulting sequences induces thus an order on the subsets, which is also called the {{em|lexicographical order}}.

In this context, one generally prefer to sort first the subsets by [[cardinality]], such as in the [[shortlex order]]. Therefore, in the following, we will consider only orders on subsets of fixed cardinal.

For example, using the natural order of the integers, the lexicographical ordering on the subsets of three elements of <math>S = \{1, 2, 3, 4, 5, 6\}</math> is

:{{math|123 < 124 < 125 < 126 < 134 < 135 < 136 < 145 < 146 < 156 <}} 
::{{math|234 < 235 < 236 < 245 < 246 < 256 < 345 < 346 < 356 < 456}}.

For ordering finite subsets of a given cardinality of the [[natural number]]s, the {{em|colexicographical}} order (see below) is often more convenient, because all [[initial segment]]s are finite, and thus the colexicographical order defines an [[order isomorphism]] between the natural numbers and the set of sets of <math>n</math> natural numbers. This is not the case for the lexicographical order, as, with the lexicographical order, we have, for example, <math>12 n < 134</math> for every <math>n > 2.</math>

==Group orders of Z<sup>''n''</sup>==

Let <math>\Z^n</math> be the [[free Abelian group]] of rank <math>n,</math> whose elements are sequences of <math>n</math> integers, and operation is the [[Additive group|addition]]. A [[Totally ordered group|group order]] on <math>\Z^n</math> is a [[total order]], which is compatible with addition, that is 
<math display=block>a < b \quad \text{ if and only if } \quad a+c < b+c.</math>

The lexicographical ordering is a group order on <math>\Z^n.</math>

The lexicographical ordering may also be used to characterize all group orders on <math>\Z^n.</math><ref>Robbiano, L. (1985). Term orderings on the polynomial ring. In ''European Conference on Computer Algebra'' (pp. 513-517). Springer Berlin Heidelberg.</ref><ref>{{citation
 | last = Weispfenning | first = Volker
 | date = May 1987
 | doi = 10.1145/24554.24557
 | issue = 2
 | journal = SIGSAM Bulletin
 | location = New York, NY, USA
 | pages = 16–18
 | publisher = ACM
 | title = Admissible Orders and Linear Forms
 | volume = 21| s2cid = 10226875
 | doi-access = free
 }}.</ref> In fact, <math>n</math> [[linear form]]s with [[real number|real]] coefficients, define a map from <math>\Z^n</math> into <math>\R^n,</math> which is injective if the forms are [[linearly independent]] (it may be also injective if the forms are dependent, see below). The lexicographic order on the image of this map induces a group order on <math>\Z^n.</math> Robbiano's theorem is that every group order may be obtained in this way.

More precisely, given a group order on <math>\Z^n,</math> there exist an integer <math>s \leq n</math> and <math>s</math> linear forms with real coefficients, such that the induced map <math>\varphi</math> from <math>\Z^n</math> into <math>\R^s</math> has the following properties;

* <math>\varphi</math> is injective;
* the resulting isomorphism from <math>\Z^n</math> to the image of <math>\varphi</math> is an order isomorphism when the image is equipped with the lexicographical order on <math>\R^s.</math>

==Colexicographic order==
[[File:Orderings; permutations 5-cycle.svg|thumb|340px|Orderings of the 24 permutations of {1,...,5} that are [[Cycles and fixed points|5-cycles]] (in blue). The [[Inversion (discrete mathematics)|inversion vectors]] (in red) of permutations in ''colex'' order are in ''revcolex'' order, and vice versa.]]

The '''colexicographic''' or '''colex order''' is a variant of the lexicographical order that is obtained by reading finite sequences from the right to the left instead of reading them from the left to the right.  More precisely, whereas the lexicographical order between two sequences is defined by

:{{math|''a''<sub>1</sub>''a''<sub>2</sub>...''a''<sub>''k''</sub> <<sup>lex</sup> ''b''<sub>1</sub>''b''<sub>2</sub> ... ''b''<sub>''k''</sub>}} if {{math|''a<sub>i</sub>'' < ''b<sub>i</sub>''}} for the first {{math|''i''}} where {{math|''a<sub>i</sub>''}} and {{math|''b<sub>i</sub>''}} differ,
the colexicographical order is defined by

:{{math|''a''<sub>1</sub>''a''<sub>2</sub>...''a''<sub>''k''</sub> <<sup>colex</sup> ''b''<sub>1</sub>''b''<sub>2</sub>...''b''<sub>''k''</sub>}} if {{math|''a<sub>i</sub>'' < ''b<sub>i</sub>''}} for the last {{math|''i''}} where {{math|''a<sub>i</sub>''}} and {{math|''b<sub>i</sub>''}} differ

In general, the difference between the colexicographical order and the lexicographical order is not very significant. However, when considering increasing sequences, typically for coding subsets, the two orders differ significantly.

For example, for ordering the increasing sequences (or the sets) of two natural integers, the lexicographical order begins by

:{{math|12 < 13 < 14 < 15 < ... < 23 < 24 < 25 < ... < 34 < 35 < ... < 45 < ...}}, 

and the colexicographic order begins by

:{{math|12 < 13 < 23 < 14 < 24 < 34 < 15 < 25 < 35 < 45 < ...}}.

The main property of the colexicographical order for increasing sequences of a given length is that every [[initial segment]] is finite. In other words, the colexicographical order for increasing sequences of a given length induces an [[order isomorphism]] with the natural numbers, and allows enumerating these sequences. This is frequently used in [[combinatorics]], for example in the proof of the [[Kruskal–Katona theorem]].

==Monomials==
{{Main|Monomial order}}
When considering [[polynomial]]s, the order of the terms does not matter in general, as the addition is commutative. However, some [[algorithm]]s, such as [[polynomial long division]], require the terms to be in a specific order. Many of the main algorithms for [[multivariate polynomial]]s are related with [[Gröbner bases]], concept that requires the choice of a [[monomial order]], that is a [[total order]], which is compatible with the [[monoid]] structure of the [[monomials]]. Here "compatible" means that <math>a < b \text{ implies } ac < bc,</math> if the monoid operation is denoted multiplicatively. This compatibility implies that the product of a polynomial by a monomial does not change the order of the terms. For Gröbner bases, a further condition must be satisfied, namely that every non-constant monomial is greater than the monomial {{math|1}}. However this condition is not needed for other related algorithms, such as the algorithms for the computation of the [[tangent cone#Definition in algebraic geometry|tangent cone]].

As Gröbner bases are defined for polynomials in a fixed number of variables, it is common to identify monomials (for example <math>x_1 x_2^3 x_4 x_5^2</math>) with their exponent vectors (here {{math|[1, 3, 0, 1, 2]}}). If {{math|''n''}} is the number of variables, every monomial order is thus the restriction to <math>\N^n</math> of a monomial order of <math>\Z^n</math> (see above {{slink||Group orders of Zn}} <math>\Z^n,</math> for a classification).

One of these admissible orders is the lexicographical order. It is, historically, the first to have been used for defining Gröbner bases, and is sometimes called {{em|pure lexicographical order}} for distinguishing it from other orders that are also related to a lexicographical order.

Another one consists in comparing first the [[total degree]]s, and then resolving the conflicts by using the lexicographical order. This order is not widely used, as either the lexicographical order or the degree reverse lexicographical order have generally better properties.

The {{em|degree reverse lexicographical order}} consists also in comparing first the total degrees, and, in case of equality of the total degrees, using the reverse of the colexicographical order. That is, given two exponent vectors, one has 
<math display=block>[a_1, \ldots, a_n] < [b_1, \ldots, b_n]</math>
if either 
<math display=block>a_1+ \cdots+ a_n < b_1+ \cdots+ b_n,</math>
or
<math display=block> 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.</math>

For this ordering, the monomials of degree one have the same order as the corresponding indeterminates (this would not be the case if the reverse lexicographical order would be used).  For comparing monomials in two variables of the same total degree, this order is the same as the lexicographic order. This is not the case with more variables. For example, for exponent vectors of monomials of degree two in three variables, one has for the degree reverse lexicographic order:
<math display=block>[0, 0, 2] < [0, 1, 1] < [1, 0, 1] < [0, 2, 0] < [1, 1, 0] < [2, 0, 0]</math>

For the lexicographical order, the same exponent vectors are ordered as
<math display=block>[0, 0, 2] < [0, 1, 1] < [0, 2, 0] < [1, 0, 1] < [1, 1, 0] < [2, 0, 0].</math>

A useful property of the degree reverse lexicographical order is that a [[homogeneous polynomial]] is a multiple of the least indeterminate if and only if its leading monomial (its greater monomial) is a multiple of this least indeterminate.

==See also==

* [[Collation]]
* [[Kleene–Brouwer order]]
* [[Lexicographic preferences]] - an application of lexicographic order in economics.
* [[Lexicographic optimization]] - an algorithmic problem of finding a lexicographically-maximal element.
* [[Lexicographic order topology on the unit square]]
* [[Abstract index notation#Braiding|Lexicographic ordering in tensor abstract index notation]]
* [[Lexicographically minimal string rotation]]
* [[Leximin order]]
* [[Long line (topology)]]
* [[Lyndon word]]
* [[Tree_traversal#Pre-order,_NLR|Pre-order]] - the name of the lexicographical order (of bits) in a [[binary tree]] traversal
* [[Star product]], a different way of combining partial orders
* [[Shortlex order]]
* [[Total order#Orders on the Cartesian product of totally ordered sets|Orders on the Cartesian product of totally ordered sets]]

==References==
{{reflist}}

== External links ==
* {{Wikiversity-inline|Lexicographic and colexicographic order}}

[[Category:Order theory]]
[[Category:Lexicography]]