Lexicographic order


In mathematics, the lexicographic or lexicographical order is a generalization of the alphabetical order of the dictionaries to sequences 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 subsets of a given finite set by assigning a total order to the finite set, and converting subsets into increasing sequences, to which the lexicographical order is applied.
A generalization defines an order on an n-ary Cartesian product of partially ordered sets; 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 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, often called the alphabet, which is totally ordered. That is, for any two symbols and in that are not the same symbol, exactly one of or is true.
The words of are the finite sequences of symbols from, including words of length 1 containing a single symbol, words of length 2 with 2 symbols, and so on, even including the empty sequence with no symbols at all. The lexicographical order on the set of all these finite words orders the words as follows:
  1. Given two different words of the same length, say and, the order of the two words depends on the alphabetic order of the symbols in the first place where the two words differ : if and only if in the underlying order of the alphabet.
  2. If two words have different lengths, the usual lexicographical order pads the shorter one with "blanks" 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.
In lexicographical order, the word "Thomas" appears before "Thompson" because they first differ at the fifth letter, 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, the set of words of length is well-ordered by the lexicographical order ; that is, every decreasing sequence of words of length is finite. It is not true that the set of all finite words is well-ordered; for example, the infinite set of words 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 numbers is the same as the variant shortlex of the lexicographic order. In fact, with positional notation, a natural number is represented by a sequence of numerical digits, and a natural number is larger than another one if either it has more digits or the number of digits is the same and the first digit which differs is larger.
For real numbers 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 computers. This is one of the reasons for adopting two's complement representation for representing signed integers 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 computerized sorting of dates easier by avoiding the need for a separate sorting algorithm.

Monoid of words

The over an alphabet is the free monoid over. That is, the elements of the monoid are the finite sequences of elements of , and the operation is the concatenation of words. A word is a prefix of another word if there exists a word such that. By this definition, the empty word is a prefix of every word, and every word is a prefix of itself ; 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 partially or totally ordered set, and two words and over such that is non-empty, then one has under lexicographical order, if at least one of the following conditions is satisfied:
  • is a prefix of
  • there exists words,, and elements and of such that
Notice that, due to the prefix condition in this definition, where is the empty word.
If is a total order on then so is the lexicographic order on the words of However, in general this is not a well-order, even if the alphabet is well-ordered. For instance, if, the language has no least element in the lexicographical order:.
Since many applications require well orders, a variant of the lexicographical orders is often used. This well-order, sometimes called or, consists in considering first the lengths of the words, and, if the lengths are equal, using the lexicographical order. If the order on is a well-order, the same is true for the shortlex order.

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 is a sequence whose th element belongs to for every 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 sets and the is defined as
The result is a partial order. If and are each 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 numbers, 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 is not well-ordered; the subset of sequences that have precisely one does not have a least element under the lexicographical order induced by because is an infinite descending chain. Similarly, the infinite lexicographic product is not Noetherian either because is an infinite ascending chain.

Functions over a well-ordered set

The functions from a well-ordered set to a totally ordered set may be identified with sequences indexed by of elements of They can thus be ordered by the lexicographical order, and for two such functions and the lexicographical order is thus determined by their values for the smallest such that
If is also well-ordered and is finite, then the resulting order is a well-order. As shown above, if is infinite this is not the case.

Finite subsets

In combinatorics, one has often to enumerate, and therefore to order the finite subsets of a given set For this, one usually chooses an order on Then, sorting a subset of is equivalent to converting it into an increasing sequence. The lexicographic order on the resulting sequences induces thus an order on the subsets, which is also called the.
In this context, one generally prefers 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 is
For ordering finite subsets of a given cardinality of the natural numbers, the order is often more convenient, because all initial segments are finite, and thus the colexicographical order defines an order isomorphism between the natural numbers and the set of sets of natural numbers. This is not the case for the lexicographical order, as, with the lexicographical order, we have, for example, for every

Group orders of Z''n''

Let be the free Abelian group of rank whose elements are sequences of integers, and operation is the addition. A group order on is a total order, which is compatible with addition, that is
The lexicographical ordering is a group order on
The lexicographical ordering may also be used to characterize all group orders on In fact, linear forms with real coefficients, define a map from into which is injective if the forms are linearly independent. The lexicographic order on the image of this map induces a group order on Robbiano's theorem is that every group order may be obtained in this way.
More precisely, given a group order on there exist an integer and linear forms with real coefficients, such that the induced map from into has the following properties;
  • is injective;
  • the resulting isomorphism from to the image of is an order isomorphism when the image is equipped with the lexicographical order on