Editing Lexicographic order (section)

==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.