In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the
alphabetical order
Alphabetical order is a system whereby character strings are placed in order based on the position of the characters in the conventional ordering of an alphabet. It is one of the methods of collation. In mathematics, a lexicographical order is ...
of the
dictionaries
A dictionary is a listing of lexemes from the lexicon of one or more specific languages, often arranged alphabetically (or by radical and stroke for ideographic languages), which may include information on definitions, usage, etymologies ...
to
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
s of ordered symbols or, more generally, of elements of a
totally ordered set
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexi ...
.
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
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset o ...
s of a given
finite set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. ...
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 a
Cartesian product
In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is
: A\tim ...
of
partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) 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 ...
s; this order is a total order if and only if all factors of the Cartesian product are totally ordered.
Motivation and definition
The words in a
lexicon
A lexicon is the vocabulary of a language or branch of knowledge (such as nautical or medical). In linguistics, a lexicon is a language's inventory of lexemes. The word ''lexicon'' derives from Greek word (), neuter of () meaning 'of or for w ...
(the set of words used in some language) have a conventional ordering, used in
dictionaries
A dictionary is a listing of lexemes from the lexicon of one or more specific languages, often arranged alphabetically (or by radical and stroke for ideographic languages), which may include information on definitions, usage, etymologies ...
and
encyclopedias
An encyclopedia (American English) or encyclopædia (British English) is a reference work or compendium providing summaries of knowledge either general or special to a particular field or discipline. Encyclopedias are divided into artic ...
, 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
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. ...
, often called the
alphabet
An alphabet is a standardized set of basic written graphemes (called letter (alphabet), letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character ...
, which is
totally ordered
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexiv ...
. That is, for any two symbols and in that are not the same symbol, either or .
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:
# 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 (counting from the beginning of the words): if and only if in the underlying order of the alphabet .
# 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 ) 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 ('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 , the set of words of length is
well-order
In mathematics, a well-order (or well-ordering or well-order relation) on a set ''S'' is a total order on ''S'' with the property that every non-empty subset of ''S'' has a least element in this ordering. The set ''S'' together with the well-or ...
ed by the lexicographical order (provided the alphabet is finite); that is, every decreasing sequence of words of length is finite (or equivalently, every non-empty subset has a least element). 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
Roman numerals are a numeral system that originated in ancient Rome and remained the usual way of writing numbers throughout Europe well into the Late Middle Ages. Numbers are written with combinations of letters from the Latin alphabet, eac ...
is that it is not always immediately obvious which of two numbers is the smaller. On the other hand, with the
positional notation
Positional notation (or place-value notation, or positional numeral system) usually denotes the extension to any base of the Hindu–Arabic numeral system (or decimal system). More generally, a positional system is a numeral system in which the ...
of the
Hindu–Arabic numeral system
The Hindu–Arabic numeral system or Indo-Arabic numeral system Audun HolmeGeometry: Our Cultural Heritage 2000 (also called the Hindu numeral system or Arabic numeral system) is a positional decimal numeral system, and is the most common system ...
, comparing numbers is easy, because the natural order on
nonnegative integer
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal ...
s is the same as the variant shortlex of the lexicographic order. In fact, with positional notation, a nonnegative integer is represented by a sequence of
numerical digit
A numerical digit (often shortened to just digit) is a single symbol used alone (such as "2") or in combinations (such as "25"), to represent numbers in a positional numeral system. The name "digit" comes from the fact that the ten digits (Latin ...
s, and an integer 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
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every r ...
s written in
decimal notation
The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers of the Hindu–Arabic numeral ...
, 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 (testing the sign takes some time). This is one of the reasons for adopting
two's complement
Two's complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with equivalent (but negative) value, using the binary digit with the greatest place value (the leftmost bit in big- endian ...
representation for representing
signed integer
In computer science, an integer is a datum of integral data type, a data type that represents some range of mathematical integers. Integral data types may be of different sizes and may or may not be allowed to contain negative values. Integers a ...
s in computers.
Another example of a non-dictionary use of lexicographical ordering appears in the
ISO 8601
ISO 8601 is an international standard covering the worldwide exchange and communication of date and time-related data. It is maintained by the Geneva-based International Organization for Standardization (ISO) and was first published in 1988, wi ...
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
Chronology (from Latin ''chronologia'', from Ancient Greek , ''chrónos'', "time"; and , ''-logia'') is the science of arranging events in their order of occurrence in time. Consider, for example, the use of a timeline or sequence of events. It ...
: 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 In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero elem ...
over . That is, the elements of the monoid are the finite sequences (words) of elements of (including the empty sequence, of length 0), and the operation (multiplication) is the
concatenation
In formal language theory and computer programming, string concatenation is the operation of joining character strings end-to-end. For example, the concatenation of "snow" and "ball" is "snowball". In certain formalisations of concatena ...
of words. A word is a
prefix
A prefix is an affix which is placed before the stem of a word. Adding it to the beginning of one word changes it into another word. For example, when the prefix ''un-'' is added to the word ''happy'', it creates the word ''unhappy''. Particula ...
(or 'truncation') 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 (with ); 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
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexiv ...
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 , , (possibly empty) 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
In mathematics, a well-order (or well-ordering or well-order relation) on a set ''S'' is a total order on ''S'' with the property that every non-empty subset of ''S'' has a least element in this ordering. The set ''S'' together with the well-or ...
, even if the alphabet is well-ordered. For instance, if , the
language
Language is a structured system of communication. The structure of a language is its grammar and the free components are its vocabulary. Languages are the primary means by which humans communicate, and may be conveyed through a variety of met ...
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 (if , then ), 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 a
Cartesian product
In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is
: A\tim ...
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 set
In mathematics, especially order theory, a partially ordered set (also poset) 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 ...
s and the is defined as
The result is a partial order. If and are each
totally ordered
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexiv ...
, then the result is a total order as well. The lexicographical order of two totally ordered sets is thus a
linear extension
In order theory, a branch of mathematics, a linear extension of a partial order is a total order (or linear order) that is compatible with the partial order. As a classic example, the lexicographic order of totally ordered sets is a linear extens ...
of their
product order
In mathematics, given two preordered sets A and B, the product order (also called the coordinatewise orderDavey & Priestley, '' Introduction to Lattices and Order'' (Second Edition), 2002, p. 18 or componentwise order) is a partial ordering ...
.
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
nonnegative integers
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal n ...
, 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
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural number ...
binary sequences (by definition, the set of functions from non-negative integers to also known as the
Cantor space In mathematics, a Cantor space, named for Georg Cantor, is a topological abstraction of the classical Cantor set: a topological space is a Cantor space if it is homeomorphic to the Cantor set. In set theory, the topological space 2ω is called "the ...
) is not well-ordered; the subset of sequences that have precisely one (that is, ) does not have a least element under the lexicographical order induced by because is an
infinite descending chain
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive ...
. Similarly, the infinite lexicographic product is not
Noetherian In mathematics, the adjective Noetherian is used to describe objects that satisfy an ascending or descending chain condition on certain kinds of subobjects, meaning that certain ascending or descending sequences of subobjects must have finite leng ...
either because is an infinite ascending chain.
Functions over a well-ordered set
The functions from a
well-ordered set
In mathematics, a well-order (or well-ordering or well-order relation) on a set ''S'' is a total order on ''S'' with the property that every non-empty subset of ''S'' has a least element in this ordering. The set ''S'' together with the well-or ...
to a
totally ordered set
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexi ...
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
Sorting refers to ordering data in an increasing or decreasing manner according to some linear relationship among the data items.
# ordering: arranging items in a sequence ordered by some criterion;
# categorizing: grouping items with similar pr ...
a subset of 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 .
In this context, one generally prefer to sort first the subsets by
cardinality
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
, such as in the
shortlex order In mathematics, and particularly in the theory of formal languages, shortlex is a total ordering for finite sequences of objects that can themselves be totally ordered. In the shortlex ordering, sequences are primarily sorted by cardinality (length ...
. 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 number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal ...
s, the order (see below) is often more convenient, because all
initial segment
In mathematics, an upper set (also called an upward closed set, an upset, or an isotone set in ''X'') of a partially ordered set (X, \leq) is a subset S \subseteq X with the following property: if ''s'' is in ''S'' and if ''x'' in ''X'' is larger ...
s are finite, and thus the colexicographical order defines an
order isomorphism
In the mathematical field of order theory, an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets (posets). Whenever two posets are order isomorphic, they can be con ...
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
In mathematics, a free abelian group is an abelian group with a basis. Being an abelian group means that it is a set with an addition operation that is associative, commutative, and invertible. A basis, also called an integral basis, is a sub ...
of rank whose elements are sequences of integers, and operation is the
addition
Addition (usually signified by the plus symbol ) is one of the four basic operations of arithmetic, the other three being subtraction, multiplication and division. The addition of two whole numbers results in the total amount or '' sum'' of ...
. A
group order
In mathematics, the order of a finite group is the number of its elements. If a group is not finite, one says that its order is ''infinite''. The ''order'' of an element of a group (also called period length or period) is the order of the subg ...
on is a
total order
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexi ...
, 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 form
In mathematics, a linear form (also known as a linear functional, a one-form, or a covector) is a linear map from a vector space to its field of scalars (often, the real numbers or the complex numbers).
If is a vector space over a field , the s ...
s with
real
Real may refer to:
Currencies
* Brazilian real (R$)
* Central American Republic real
* Mexican real
* Portuguese real
* Spanish real
* Spanish colonial real
Music Albums
* ''Real'' (L'Arc-en-Ciel album) (2000)
* ''Real'' (Bright album) (2010) ...
coefficients, define a map from into which is injective if the forms are
linearly independent
In the theory of vector spaces, a set of vectors is said to be if there is a nontrivial linear combination of the vectors that equals the zero vector. If no such linear combination exists, then the vectors are said to be . These concepts ar ...
(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 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
Colexicographic order
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
: if for the first where and differ,
the colexicographical order is defined by
: if for the last where and 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
:,
and the colexicographic order begins by
:.
The main property of the colexicographical order for increasing sequences of a given length is that every
initial segment
In mathematics, an upper set (also called an upward closed set, an upset, or an isotone set in ''X'') of a partially ordered set (X, \leq) is a subset S \subseteq X with the following property: if ''s'' is in ''S'' and if ''x'' in ''X'' is larger ...
is finite. In other words, the colexicographical order for increasing sequences of a given length induces an
order isomorphism
In the mathematical field of order theory, an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets (posets). Whenever two posets are order isomorphic, they can be con ...
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
When considering
polynomial
In mathematics, a polynomial is an expression (mathematics), expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addition, subtrac ...
s, the order of the terms does not matter in general, as the addition is commutative. However, some
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
s, such as
polynomial long division
In algebra, polynomial long division is an algorithm for dividing a polynomial by another polynomial of the same or lower degree, a generalized version of the familiar arithmetic technique called long division. It can be done easily by hand, becau ...
, require the terms to be in a specific order. Many of the main algorithms for
multivariate polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
s are related with Gröbner bases, concept that requires the choice of a
monomial order
In mathematics, a monomial order (sometimes called a term order or an admissible order) is a total order on the set of all ( monic) monomials in a given polynomial ring, satisfying the property of respecting multiplication, i.e.,
* If u \leq v an ...
, that is a
total order
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexi ...
, which is compatible with the
monoid
In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.
Monoids a ...
structure of the
monomials
In mathematics, a monomial is, roughly speaking, a polynomial which has only one term. Two definitions of a monomial may be encountered:
# A monomial, also called power product, is a product of powers of variables with nonnegative integer expone ...
. Here "compatible" means that 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 . However this condition is not needed for other related algorithms, such as the algorithms for the computation of the
tangent cone
In geometry, the tangent cone is a generalization of the notion of the tangent space to a manifold to the case of certain spaces with singularities.
Definitions in nonlinear analysis
In nonlinear analysis, there are many definitions for a tangen ...
.
As Gröbner bases are defined for polynomials in a fixed number of variables, it is common to identify monomials (for example ) with their exponent vectors (here ). If is the number of variables, every monomial order is thus the restriction to of a monomial order of (see above 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 for distinguishing it from other orders that are also related to a lexicographical order.
Another one consists in comparing first the
total degree
In mathematics, the degree of a polynomial is the highest of the degrees of the polynomial's monomials (individual terms) with non-zero coefficients. The degree of a term is the sum of the exponents of the variables that appear in it, and thus ...
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 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