{"history":[],"article":{"id":"e4ef8367-69b3-4efc-8b2b-818a81dabc9f","title":"Lexicographic order","slug":"lexicographic-order","content":":::summary\n:::\n\n# \nIn [mathematics](https://bliptext.com/articles/mathematics), the **lexicographic** or **lexicographic**al order (also known as **lexical order**, or **dictionary order**) is a generalization of the [alphabetical order](https://bliptext.com/articles/alphabetical-order) of the [dictionaries](https://bliptext.com/articles/dictionaries) to [sequences](https://bliptext.com/articles/sequence) of ordered symbols or, more generally, of elements of a [totally ordered set](https://bliptext.com/articles/totally-ordered-set).\nThere are several variants and generalizations of the lexicographical ordering.\nOne variant applies to sequences of different lengths by comparing the lengths of the sequences before considering their elements.\nAnother variant, widely used in [combinatorics](https://bliptext.com/articles/combinatorics), orders [subsets](https://bliptext.com/articles/subset) of a given [finite set](https://bliptext.com/articles/finite-set) by assigning a total order to the [finite set](https://bliptext.com/articles/finite-set), and converting [subsets](https://bliptext.com/articles/subset) into [increasing sequences](https://bliptext.com/articles/sequence), to which the lexicographical order is applied.\nA generalization defines an order on an n-ary [Cartesian product](https://bliptext.com/articles/cartesian-product) of [partially ordered sets](https://bliptext.com/articles/partially-ordered-set); this order is a total order if and only if all factors of the [Cartesian product](https://bliptext.com/articles/cartesian-product) are totally ordered.\n\n# Definition\nThe words in a [lexicon](https://bliptext.com/articles/lexicon) (the set of words used in some language) have a conventional ordering, used in [dictionaries](https://bliptext.com/articles/dictionaries) and [encyclopedias](https://bliptext.com/articles/encyclopedias), that depends on the underlying ordering of the alphabet of symbols used to build the words.\nThe lexicographical order is one way of formalizing word order given the order of the underlying symbols.\nThe formal notion starts with a [finite set](https://bliptext.com/articles/finite-set)\nA\n, often called the [alphabet](https://bliptext.com/articles/alphabet-formal-languages), which is [totally ordered](https://bliptext.com/articles/totally-ordered).\nThat is, for any two symbols\na\nand\nb\nin\nA\nthat are not the same symbol, either\na < b\nor\nb < a\n.\nThe words of\nA\nare the finite sequences of symbols from\nA\n, including words of length 1 containing a single symbol, words of length 2 with 2 symbols, and so on, even including the empty sequence \\varepsilon with no symbols at all.\nThe lexicographical order on the set of all these finite words orders the words as follows:\nand\n, the order of the two words depends on the alphabetic order of the symbols in the first place\ni\nwhere the two words differ (counting from the beginning of the words):\na < b\nif and only if\nai < bi\nin the underlying order of the alphabet\nA\n.\nA\n) at the end until the words are the same length, and then the words are compared as in the previous case.\nHowever, in [combinatorics](https://bliptext.com/articles/combinatorics), another convention is frequently used for the second case, whereby a shorter sequence is always smaller than a longer sequence.\nThis variant of the lexicographical order is sometimes called.\nIn 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.\nBecause it is the first difference, in this case the 5th letter is the \"most significant difference\" for alphabetical ordering.\nAn important property of the lexicographical order is that for each\nn\n, the set of words of length\nn\nis [well-ordered](https://bliptext.com/articles/well-order) by the lexicographical order (provided the alphabet is finite); that is, every decreasing sequence of words of length\nn\nis finite (or equivalently, every non-empty subset has a least element).\nIt 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.\n\n# Numeral systems and dates\nThe lexicographical order is used not only in dictionaries, but also commonly for numbers and dates.\nOne of the drawbacks of the [Roman numeral system](https://bliptext.com/articles/roman-numeral-system) is that it is not always immediately obvious which of two numbers is the smaller.\nOn the other hand, with the [positional notation](https://bliptext.com/articles/positional-notation) of the [Hindu–Arabic numeral system](https://bliptext.com/articles/hindu-arabic-numeral-system), comparing numbers is easy, because the natural order on [natural numbers](https://bliptext.com/articles/natural-number) is the same as the variant [shortlex](https://bliptext.com/articles/shortlex-order) of the lexicographic order.\nIn fact, with positional notation, a natural number is represented by a sequence of [numerical digits](https://bliptext.com/articles/numerical-digit), 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.\nFor [real numbers](https://bliptext.com/articles/real-number) written in [decimal notation](https://bliptext.com/articles/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.\nThe padding 'blank' in this context is a trailing \"0\" digit.\nWhen negative numbers are also considered, one has to reverse the order for comparing negative numbers.\nThis is not usually a problem for humans, but it may be for [computers](https://bliptext.com/articles/computer) (testing the sign takes some time).\nThis is one of the reasons for adopting [two's complement](https://bliptext.com/articles/two-s-complement) representation for representing [signed integers](https://bliptext.com/articles/signed-integer) in computers.\nAnother example of a non-dictionary use of lexicographical ordering appears in the [ISO 8601](https://bliptext.com/articles/iso-8601) standard for dates, which expresses a date as YYYY-MM-DD.\nThis formatting scheme has the advantage that the lexicographical order on sequences of characters that represent dates coincides with the [chronological order](https://bliptext.com/articles/chronological-order): an earlier CE date is smaller in the lexicographical order than a later date up to year 9999.\nThis date ordering makes [computerized sorting](https://bliptext.com/articles/sorting-algorithm) of dates easier by avoiding the need for a separate sorting algorithm.\n\n# Monoid of words\nThe over an alphabet\nA\nis the [free monoid](https://bliptext.com/articles/free-monoid) over\nA\n. That is, the elements of the monoid are the finite sequences (words) of elements of\nA\n(including the empty sequence, of length 0), and the operation (multiplication) is the [concatenation](https://bliptext.com/articles/concatenation) of words.\nA word\nu\nis a [prefix](https://bliptext.com/articles/prefix-computer-science) (or 'truncation') of another word\nv\nif there exists a word\nw\nsuch that\nv = uw\n. By this definition, the empty word (\\varepsilon) is a prefix of every word, and every word is a prefix of itself (with\nw\n); care must be taken if these cases are to be excluded.\nWith this terminology, the above definition of the lexicographical order becomes more concise: Given a [partially](https://bliptext.com/articles/partial-order) or [totally ordered](https://bliptext.com/articles/total-order) set\nA\n, and two words\na\nand\nb\nover\nA\nsuch that\nb\nis non-empty, then one has\na < b\nunder lexicographical order, if at least one of the following conditions is satisfied:\na\nis a prefix of\nb\nu\n,\nv\n,\nw\n(possibly empty) and elements\nx\nand\ny\nof\nA\nsuch that\nx < y\na = uxv\nb = uyw\nNotice that, due to the prefix condition in this definition, where \\varepsilon is the empty word.\nIf \\,<\\, is a total order on A, then so is the lexicographic order on the words of A. However, in general this is not a [well-order](https://bliptext.com/articles/well-order), even if the alphabet A is [well-order](https://bliptext.com/articles/well-order)ed.\nFor instance, if\nA = {a, b}\n, the [language](https://bliptext.com/articles/formal-language)\n{anb\nhas no least element in the lexicographical order:\n... < aab < ab < b\n.\nSince many applications require well orders, a variant of the lexicographical orders is often used.\nThis well-order, sometimes called or, consists in considering first the lengths of the words (if\nlength(a) < length(b)\n, then a < b), and, if the lengths are equal, using the lexicographical order. If the order on\nA\nis a well-order, the same is true for the shortlex order.\n\n# Cartesian products\nThe lexicographical order defines an order on an n-ary [Cartesian product](https://bliptext.com/articles/cartesian-product) of ordered sets, which is a total order when all these sets are themselves totally ordered.\nAn element of a Cartesian product is a sequence whose ith element belongs to E_i for every i. 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.\nSpecifically, given two [partially ordered sets](https://bliptext.com/articles/partially-ordered-set) A and B, the A \\times B is defined as\nThe result is a partial order.\nIf A and B are each [totally ordered](https://bliptext.com/articles/total-order), then the result is a total order as well.\nThe lexicographical order of two totally ordered sets is thus a [linear extension](https://bliptext.com/articles/linear-extension) of their [product order](https://bliptext.com/articles/product-order).\nOne 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](https://bliptext.com/articles/natural-number), or more generally by a well-ordered set.\nThis generalized lexicographical order is a total order if each factor set is totally ordered.\nUnlike the finite case, an infinite product of well-orders is not necessarily well-ordered by the lexicographical order.\nFor instance, the set of [countably infinite](https://bliptext.com/articles/countably-infinite) binary sequences (by definition, the set of functions from natural numbers to \\{ 0, 1 \\}, also known as the [Cantor space](https://bliptext.com/articles/cantor-space) ) is not well-ordered; the subset of sequences that have precisely one 1 (that is,\n{ 100000..., 010000..., 001000..., ... }\n) does not have a least element under the lexicographical order induced by 0 < 1, because\n100000... > 010000... > 001000... > ...\nis an [infinite descending chain](https://bliptext.com/articles/infinite-descending-chain).\nSimilarly, the infinite lexicographic product is not [Noetherian](https://bliptext.com/articles/noetherian-relation) either because\n011111... < 101111... < 110111 ... < ...\nis an infinite ascending chain.\n\n# Functions over a well-ordered set\nThe functions from a [well-ordered set](https://bliptext.com/articles/well-ordered-set) X to a [totally ordered set](https://bliptext.com/articles/totally-ordered-set) Y may be identified with sequences indexed by X of elements of Y. They can thus be ordered by the lexicographical order, and for two such functions f and g, the lexicographical order is thus determined by their values for the smallest x such that\nIf Y is also well-ordered and X is finite, then the resulting order is a well-order.\nAs shown above, if X is infinite this is not the case.\n\n# Finite subsets\nIn [combinatorics](https://bliptext.com/articles/combinatorics), one has often to enumerate, and therefore to order the [finite subsets](https://bliptext.com/articles/finite-subset) of a given set S. For this, one usually chooses an order on S. Then, [sorting](https://bliptext.com/articles/sorting) a subset of S is equivalent to convert it into an increasing sequence.\nThe lexicographic order on the resulting sequences induces thus an order on the subsets, which is also called the.\nIn this context, one generally prefer to sort first the subsets by [cardinality](https://bliptext.com/articles/cardinality), such as in the [shortlex order](https://bliptext.com/articles/shortlex-order).\nTherefore, in the following, we will consider only orders on subsets of fixed cardinal.\nFor example, using the natural order of the integers, the lexicographical ordering on the subsets of three elements of is\n123 < 124 < 125 < 126 < 134 < 135 < 136 < 145 < 146 < 156 <\n234 < 235 < 236 < 245 < 246 < 256 < 345 < 346 < 356 < 456\n.\nFor ordering finite subsets of a given cardinality of the [natural numbers](https://bliptext.com/articles/natural-number), the order (see below) is often more convenient, because all [initial segments](https://bliptext.com/articles/initial-segment) are finite, and thus the colexicographical order defines an [order isomorphism](https://bliptext.com/articles/order-isomorphism) between the [natural numbers](https://bliptext.com/articles/natural-number) and the set of sets of n [natural numbers](https://bliptext.com/articles/natural-number).\nThis is not the case for the lexicographical order, as, with the lexicographical order, we have, for example, 12 n 2.\n# [Orderings of the 3-subsets of represented as sets of red squares, increasing sequences (in blue), or by their indicator functions, converted in decimal notation (in grey). The grey numbers are also the rank of the subsets in all subsets of 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 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. | upload.wikimedia.org/wikipedia/commons/1/1c/Orderings%3B///6///choose///3.svg]\n\n# Group orders of Zn\nLet \\Z^n be the [free Abelian group](https://bliptext.com/articles/free-abelian-group) of rank n, whose elements are sequences of n integers, and operation is the [addition](https://bliptext.com/articles/additive-group).\nA [group order](https://bliptext.com/articles/totally-ordered-group) on \\Z^n is a [total order](https://bliptext.com/articles/total-order), which is compatible with addition, that is\nThe lexicographical ordering is a group order on \\Z^n.\nThe lexicographical ordering may also be used to characterize all group orders on \\Z^n.\nIn fact, n [linear forms](https://bliptext.com/articles/linear-form) with [real](https://bliptext.com/articles/real-number) coefficients, define a map from \\Z^n into \\R^n, which is injective if the forms are [linearly independent](https://bliptext.com/articles/linearly-independent) (it may be also injective if the forms are dependent, see below).\nThe lexicographic order on the image of this map induces a group order on \\Z^n.\nRobbiano's theorem is that every group order may be obtained in this way.\nMore precisely, given a group order on \\Z^n, there exist an integer s \\leq n and s linear forms with real coefficients, such that the induced map \\varphi from \\Z^n into \\R^s has the following properties;\n\n# Colexicographic order\nThe **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.\nMore precisely, whereas the lexicographical order between two sequences is defined by\na1a2...ak 001000... > ...\nis an [infinite descending chain](https://bliptext.com/articles/infinite-descending-chain).\nSimilarly, the infinite lexicographic product is not [Noetherian](https://bliptext.com/articles/noetherian-relation) either because\n011111... < 101111... < 110111 ... < ...\nis an infinite ascending chain.\n\n# Functions over a well-ordered set\nThe functions from a [well-ordered set](https://bliptext.com/articles/well-ordered-set) X to a [totally ordered set](https://bliptext.com/articles/totally-ordered-set) Y may be identified with sequences indexed by X of elements of Y. They can thus be ordered by the lexicographical order, and for two such functions f and g, the lexicographical order is thus determined by their values for the smallest x such that\nIf Y is also well-ordered and X is finite, then the resulting order is a well-order.\nAs shown above, if X is infinite this is not the case.\n\n# Finite subsets\nIn [combinatorics](https://bliptext.com/articles/combinatorics), one has often to enumerate, and therefore to order the [finite subsets](https://bliptext.com/articles/finite-subset) of a given set S. For this, one usually chooses an order on S. Then, [sorting](https://bliptext.com/articles/sorting) a subset of S is equivalent to convert it into an increasing sequence.\nThe lexicographic order on the resulting sequences induces thus an order on the subsets, which is also called the.\nIn this context, one generally prefer to sort first the subsets by [cardinality](https://bliptext.com/articles/cardinality), such as in the [shortlex order](https://bliptext.com/articles/shortlex-order).\nTherefore, in the following, we will consider only orders on subsets of fixed cardinal.\nFor example, using the natural order of the integers, the lexicographical ordering on the subsets of three elements of is\n123 < 124 < 125 < 126 < 134 < 135 < 136 < 145 < 146 < 156 <\n234 < 235 < 236 < 245 < 246 < 256 < 345 < 346 < 356 < 456\n.\nFor ordering finite subsets of a given cardinality of the [natural numbers](https://bliptext.com/articles/natural-number), the order (see below) is often more convenient, because all [initial segments](https://bliptext.com/articles/initial-segment) are finite, and thus the colexicographical order defines an [order isomorphism](https://bliptext.com/articles/order-isomorphism) between the [natural numbers](https://bliptext.com/articles/natural-number) and the set of sets of n [natural numbers](https://bliptext.com/articles/natural-number).\nThis is not the case for the lexicographical order, as, with the lexicographical order, we have, for example, 12 n 2.\n# [Orderings of the 3-subsets of represented as sets of red squares, increasing sequences (in blue), or by their indicator functions, converted in decimal notation (in grey). The grey numbers are also the rank of the subsets in all subsets of 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 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. | upload.wikimedia.org/wikipedia/commons/1/1c/Orderings%3B///6///choose///3.svg]\n\n# Group orders of Zn\nLet \\Z^n be the [free Abelian group](https://bliptext.com/articles/free-abelian-group) of rank n, whose elements are sequences of n integers, and operation is the [addition](https://bliptext.com/articles/additive-group).\nA [group order](https://bliptext.com/articles/totally-ordered-group) on \\Z^n is a [total order](https://bliptext.com/articles/total-order), which is compatible with addition, that is\nThe lexicographical ordering is a group order on \\Z^n.\nThe lexicographical ordering may also be used to characterize all group orders on \\Z^n.\nIn fact, n [linear forms](https://bliptext.com/articles/linear-form) with [real](https://bliptext.com/articles/real-number) coefficients, define a map from \\Z^n into \\R^n, which is injective if the forms are [linearly independent](https://bliptext.com/articles/linearly-independent) (it may be also injective if the forms are dependent, see below).\nThe lexicographic order on the image of this map induces a group order on \\Z^n.\nRobbiano's theorem is that every group order may be obtained in this way.\nMore precisely, given a group order on \\Z^n, there exist an integer s \\leq n and s linear forms with real coefficients, such that the induced map \\varphi from \\Z^n into \\R^s has the following properties;\n\n# Colexicographic order\nThe **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.\nMore precisely, whereas the lexicographical order between two sequences is defined by\na1a2...ak

History