Lexicographical order
Encyclopedia
In mathematics
, the lexicographic or lexicographical order, (also known as lexical order, dictionary order, alphabetical order or lexicographic(al) product), is a generalization of the way the alphabetical order of words is based on the alphabetical order of letters.
s A and B, the lexicographical order
on the Cartesian product
A × B is defined as ≤ (a′,b′) if and only if a < a′ or (a = a′ and b ≤ b′).
The result is a partial order. If A and B are totally ordered
, then the result is a total order as well.
More generally, one can define the lexicographic order on the Cartesian product of n ordered sets, on the Cartesian product of a countably infinite family of ordered sets, and on the union of such sets.
: a sequence of letters (that is, a word)
appears in a dictionary before a sequence
if and only if the first ai, which is different from bi, comes before bi in the alphabet
. That assumes both have the same length. What is usually done is to pad out the shorter word with symbols for 'blanks', and consider that a blank is a new minimum ('bottom') element.
For the purpose of dictionaries, etc., one may assume that all words have the same length, by adding blank spaces at the end, and considering the blank space as a special character that comes before any other letter in the alphabet. This also allows ordering phrases. See alphabetical order.
An important property of the lexicographical order is that it preserves well-order
s, that is, if A and B are well-ordered sets, then the product set A × B with the lexicographical order is also well-ordered.
An important exploitation of lexicographical ordering is expressed in the ISO 8601
date formatting scheme, which expresses a date as YYYY-MM-DD. This date ordering lends itself to straightforward computerized sorting
of dates such that the sorting algorithm does not need to treat the numeric parts of the date string any differently from a string of non-numeric characters, and the dates will be sorted into chronological order. Note, however, that for this to work, there must always be four digits for the year, two for the month, and two for the day, so for example single-digit days must be padded with a zero yielding '01', '02', ... , '09'.
is an n-tuple of sets, with respective total orderings
The dictionary ordering
of
is then
That is, if one of the terms
and all the preceding terms are equal.
Informally,
represents the first letter,
the second and so on when looking up a word in a dictionary, hence the name.
This could be more elegantly stated by recursively defining the ordering of any set
represented by
This will satisfy
where
To put it more simply, compare the first terms. If they are equal, compare the second terms – and so on. The relationship between the first corresponding terms that are not equal determines the relationship between the entire elements.
s then the result is a non-Archimedean group
, because e.g. n(0,1) < (1,0) for all n.
If the component sets are ordered vector space
s over R (in particular just R), then the result is also an ordered vector space.
over the free monoid A* formed by the set of all finite sequences of elements in A, with sequence concatenation
as the monoid operation, as follows:
if
If < is a total order on A, then so is the lexicographic order <d on A*. If A is a finite and totally ordered alphabet, A* is the set of all words over A, and we retrieve the notion of dictionary ordering used in lexicography that gave its name to the lexicographic orderings.
However, in general this is not a well-order
, even though it is on the alphabet A; for instance, if A = {a, b}, the language
{anb | n ≥ 0} has no least element: ... <d aab <d ab <d b. A well-order for strings, based on the lexicographical order, is the shortlex order
.
Similarly we can also compare a finite and an infinite string, or two infinite strings.
Comparing strings of different lengths can also be modeled as comparing strings of infinite length by right-padding finite strings with blank spaces, if, as usual, the blank space is the least element of the alphabet (or, if it is originally not in the alphabet, adding it as least element).
If Y is also well-ordered and X is finite, then the resulting order is a well-order. As already shown above, if X is infinite this is in general not the case.
If X is infinite and Y has more than one element, then the resulting set YX is not a countable set
, see also cardinal exponentiation.
Alternatively, consider the functions f from an inversely well-ordered X to a well-ordered Y with minimum 0, restricted to those that are non-zero at only a finite subset of X. The result is well-ordered. Correspondingly we can also consider a well-ordered X and apply lexicographical order where a higher x is a more significant position. This corresponds to exponentiation of ordinal numbers YX. If X and Y are countable then the resulting set is also countable.
in a polynomial
, by ordering the monomial
s in the indeterminate
s. This is fundamental, to have a normal form
. Such matters are typically left implicit in discussion between humans, but must of course be dealt with exactly in computer algebra. In practice one has an alphabet of indeterminates X, Y, ... and orders all monomials formed from them by a variant of lexicographical order. For example if one decides to order the alphabet by
and also to look at higher terms first, that means ordering
and also
There is some flexibility in ordering monomials, and this can be exploited in Gröbner basis
theory.
like .399999... are not included in the set of strings representing numbers. With that restriction there is an order-preserving bijection between the strings and the numbers.
.
In the case of monomials one may sort the exponents downward, with the exponent of the first base variable as primary sort key, e.g.:
Alternatively, sorting may be done by the sum of the exponents, downward.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the lexicographic or lexicographical order, (also known as lexical order, dictionary order, alphabetical order or lexicographic(al) product), is a generalization of the way the alphabetical order of words is based on the alphabetical order of letters.
Definition
Given two partially ordered setPartially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
s A and B, the lexicographical order
Order theory
Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...
on the Cartesian product
Cartesian product
In mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...
A × B is defined as ≤ (a′,b′) if and only if a < a′ or (a = a′ and b ≤ b′).
The result is a partial order. If A and B are totally ordered
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
, then the result is a total order as well.
More generally, one can define the lexicographic order on the Cartesian product of n ordered sets, on the Cartesian product of a countably infinite family of ordered sets, and on the union of such sets.
Motivation and uses
The name of the lexicographic order comes from its generalizing the order given to words in a dictionaryDictionary
A dictionary is a collection of words in one or more specific languages, often listed alphabetically, with usage information, definitions, etymologies, phonetics, pronunciations, and other information; or a book of words in one language with their equivalents in another, also known as a lexicon...
: a sequence of letters (that is, a word)
- a1a2 ... ak
appears in a dictionary before a sequence
- b1b2 ... bk
if and only if the first ai, which is different from bi, comes before bi in the alphabet
Alphabet
An alphabet is a standard set of letters—basic written symbols or graphemes—each of which represents a phoneme in a spoken language, either as it exists now or as it was in the past. There are other systems, such as logographies, in which each character represents a word, morpheme, or semantic...
. That assumes both have the same length. What is usually done is to pad out the shorter word with symbols for 'blanks', and consider that a blank is a new minimum ('bottom') element.
For the purpose of dictionaries, etc., one may assume that all words have the same length, by adding blank spaces at the end, and considering the blank space as a special character that comes before any other letter in the alphabet. This also allows ordering phrases. See alphabetical order.
An important property of the lexicographical order is that it preserves well-order
Well-order
In mathematics, a well-order relation on a set S is a strict total order on S with the property that every non-empty subset of S has a least element in this ordering. Equivalently, a well-ordering is a well-founded strict total order...
s, that is, if A and B are well-ordered sets, then the product set A × B with the lexicographical order is also well-ordered.
An important exploitation of lexicographical ordering is expressed in the ISO 8601
ISO 8601
ISO 8601 Data elements and interchange formats – Information interchange – Representation of dates and times is an international standard covering the exchange of date and time-related data. It was issued by the International Organization for Standardization and was first published in 1988...
date formatting scheme, which expresses a date as YYYY-MM-DD. This date ordering lends itself to straightforward computerized sorting
Sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
of dates such that the sorting algorithm does not need to treat the numeric parts of the date string any differently from a string of non-numeric characters, and the dates will be sorted into chronological order. Note, however, that for this to work, there must always be four digits for the year, two for the month, and two for the day, so for example single-digit days must be padded with a zero yielding '01', '02', ... , '09'.
Case of multiple products
Supposeis an n-tuple of sets, with respective total orderings
The dictionary ordering
of
is then
That is, if one of the terms
and all the preceding terms are equal.
Informally,
represents the first letter,
the second and so on when looking up a word in a dictionary, hence the name.
This could be more elegantly stated by recursively defining the ordering of any set
represented by
This will satisfy
where
To put it more simply, compare the first terms. If they are equal, compare the second terms – and so on. The relationship between the first corresponding terms that are not equal determines the relationship between the entire elements.
Groups and vector spaces
If the component sets are ordered groupOrdered group
In abstract algebra, a partially-ordered group is a group equipped with a partial order "≤" that is translation-invariant; in other words, "≤" has the property that, for all a, b, and g in G, if a ≤ b then a+g ≤ b+g and g+a ≤ g+b.An element x of G is called positive element if 0 ≤ x...
s then the result is a non-Archimedean group
Archimedean group
In abstract algebra, a branch of mathematics, an Archimedean group is an algebraic structure consisting of a set together with a binary operation and binary relation satisfying certain axioms detailed below. We can also say that an Archimedean group is a linearly ordered group for which the...
, because e.g. n(0,1) < (1,0) for all n.
If the component sets are ordered vector space
Ordered vector space
In mathematics an ordered vector space or partially ordered vector space is a vector space equipped with a partial order which is compatible with the vector space operations.- Definition:...
s over R (in particular just R), then the result is also an ordered vector space.
Ordering of sequences of various lengths
Given a partially ordered set A, the above considerations allow to define naturally a lexicographical partial order over the free monoid A* formed by the set of all finite sequences of elements in A, with sequence concatenationConcatenation
In computer programming, string concatenation is the operation of joining two character strings end-to-end. For example, the strings "snow" and "ball" may be concatenated to give "snowball"...
as the monoid operation, as follows:
if
-
is a prefixPrefixA prefix is an affix which is placed before the root of a word. Particularly in the study of languages,a prefix is also called a preformative, because it alters the form of the words to which it is affixed.Examples of prefixes:...
of
, or -
and 
, where 
is the longest common prefix of 
and 
, 
and 
are members of A such that 
, and 
and 
are members of A*.
If < is a total order on A, then so is the lexicographic order <d on A*. If A is a finite and totally ordered alphabet, A* is the set of all words over A, and we retrieve the notion of dictionary ordering used in lexicography that gave its name to the lexicographic orderings.
However, in general this is not a well-order
Well-order
In mathematics, a well-order relation on a set S is a strict total order on S with the property that every non-empty subset of S has a least element in this ordering. Equivalently, a well-ordering is a well-founded strict total order...
, even though it is on the alphabet A; for instance, if A = {a, b}, the language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
{anb | n ≥ 0} has no least element: ... <d aab <d ab <d b. A well-order for strings, based on the lexicographical order, is the shortlex order
Shortlex order
The shortlex order is an ordering for ordered sets of objects, where the sequences are primarily sorted by cardinality with the shortest sequences first, and sequences of the same length are sorted into lexicographical order....
.
Similarly we can also compare a finite and an infinite string, or two infinite strings.
Comparing strings of different lengths can also be modeled as comparing strings of infinite length by right-padding finite strings with blank spaces, if, as usual, the blank space is the least element of the alphabet (or, if it is originally not in the alphabet, adding it as least element).
Generalization
Consider the set of functions f from a well-ordered set X to a totally ordered set Y. For two such functions f and g, the order is determined by the values for the smallest x such that f(x) ≠ g(x).If Y is also well-ordered and X is finite, then the resulting order is a well-order. As already shown above, if X is infinite this is in general not the case.
If X is infinite and Y has more than one element, then the resulting set YX is not a countable set
Countable set
In mathematics, a countable set is a set with the same cardinality as some subset of the set of natural numbers. A set that is not countable is called uncountable. The term was originated by Georg Cantor...
, see also cardinal exponentiation.
Alternatively, consider the functions f from an inversely well-ordered X to a well-ordered Y with minimum 0, restricted to those that are non-zero at only a finite subset of X. The result is well-ordered. Correspondingly we can also consider a well-ordered X and apply lexicographical order where a higher x is a more significant position. This corresponds to exponentiation of ordinal numbers YX. If X and Y are countable then the resulting set is also countable.
Monomials
In algebra it is traditional to order termsTerm (mathematics)
A term is a mathematical expression which may form a separable part of an equation, a series, or another expression.-Definition:In elementary mathematics, a term is either a single number or variable, or the product of several numbers or variables separated from another term by a + or - sign in an...
in a polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
, by ordering the monomial
Monomial
In mathematics, in the context of polynomials, the word monomial can have one of two different meanings:*The first is a product of powers of variables, or formally any value obtained by finitely many multiplications of a variable. If only a single variable x is considered, this means that any...
s in the indeterminate
Indeterminate
Indeterminate has a variety of meanings in mathematics:* Indeterminate * Indeterminate system* Indeterminate equation* Statically indeterminate* Indeterminate formIt is also a term in botany and gardening:*Indeterminate growth...
s. This is fundamental, to have a normal form
Normal form
Normal form may refer to:* Normal form * Normal form * Normal form * Normal form In formal language theory:* Beta normal form* Chomsky normal form* Greibach normal form* Kuroda normal form...
. Such matters are typically left implicit in discussion between humans, but must of course be dealt with exactly in computer algebra. In practice one has an alphabet of indeterminates X, Y, ... and orders all monomials formed from them by a variant of lexicographical order. For example if one decides to order the alphabet by
- X < Y < ...
and also to look at higher terms first, that means ordering
- ... < X3 < X2 < X
and also
- X < Yk for all k.
There is some flexibility in ordering monomials, and this can be exploited in Gröbner basis
Gröbner basis
In computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating subset of an ideal I in a polynomial ring R...
theory.
Decimal fractions
For decimal fractions from the decimal point, a < b applies equivalently for the numerical order and the lexicographic order, provided that numbers with a recurring decimal 90.999...
In mathematics, the repeating decimal 0.999... denotes a real number that can be shown to be the number one. In other words, the symbols 0.999... and 1 represent the same number...
like .399999... are not included in the set of strings representing numbers. With that restriction there is an order-preserving bijection between the strings and the numbers.
Reverse lexicographic order
In a common variation of lexicographic order, one compares elements by reading from the right instead of from the left, i.e., the right-most component is the most significant, e.g. applied in a rhyming dictionaryRhyming dictionary
A rhyming dictionary is a specialist dictionary designed for use in writing poetry and lyrics. In a rhyming dictionary, words are categorized into equivalence classes that consist of words which rhyme with one another...
.
In the case of monomials one may sort the exponents downward, with the exponent of the first base variable as primary sort key, e.g.:
-
.
Alternatively, sorting may be done by the sum of the exponents, downward.
See also
- CollationCollationCollation is the assembly of written information into a standard order. One common type of collation is called alphabetization, though collation is not limited to ordering letters of the alphabet...
- Colexicographical orderColexicographical orderIn mathematics, the colexicographic or colex order, is a natural order structure of the Cartesian product of two or more ordered sets. It is similar in structure to the lexicographical order...
- Lexicographic preferencesLexicographic preferencesLexicographic preferences describe comparative preferences where an economic agent infinitely prefers one good to another . Thus if offered several bundles of goods, the agent will choose the bundle that offers the most X, no matter how much Y there is...
- Orders on the Cartesian product of totally ordered sets
- Lexicographic order on the Rn
- Lexicographic order topology on the unit squareLexicographic order topology on the unit squareIn mathematics, and especially general topology, the lexicographic ordering on the unit square is an example of a topology on the unit square S, i.e...
- Long line (topology)Long line (topology)In topology, the long line is a topological space somewhat similar to the real line, but in a certain way "longer". It behaves locally just like the real line, but has different large-scale properties. Therefore it serves as one of the basic counterexamples of topology...
- Product orderProduct orderIn mathematics, given two ordered sets A and B, one can induce a partial ordering on the Cartesian product A × B. Giventwo pairs and in A × B, one sets ≤...