NationMaster - Encyclopedia: Lexicographical order

In mathematics, the lexicographic or lexicographical order, (also known as dictionary order, alphabetic order or lexicographic(al) product), is a natural order structure of the Cartesian product of two ordered sets. Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. ... In mathematics, the Cartesian product is a direct product of sets. ...

Given two partially ordered sets A and B, the lexicographical order on the Cartesian product A × B is defined as In mathematics, especially order theory, a partially ordered set (or poset) is a set equipped with a partial order relation. ...

(a,b) ≤ (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 also. In mathematics, a total order, linear order or simple order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ...

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.

1 Motivation and uses
2 Case of multiple products
3 Groups and vector spaces
4 Ordering of sequences of various lengths
5 Generalization
6 Monomials
7 Decimal fractions
8 Lexicographic order with reversed significance
9 See also

Motivation and uses

The name of the lexicographic order comes from its generalizing the order given to words in a dictionary: a sequence of letters (that is, a word) This article includes a list of works cited or a list of external links, but its sources remain unclear because it lacks in-text citations. ...

a₁a₂ ... a_k

appears in a dictionary before a sequence

b₁b₂ ... b_k

if and only if the first a_i which is different from b_i comes before b_i in the alphabet. That assumes both have the same length; what is usually done is to pad out the shorter word for symbols for 'blanks', and to consider that a blank is a new minimum ('bottom') element. For other uses, see Alphabet (disambiguation). ...

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 which comes before any other letter in the alphabet. This also allows ordering of phrases. See alphabetical order. This article needs cleanup. ...

An important property of the lexicographical order is that it preserves well-orders, that is, if A and B are well-ordered sets, then the product set A × B with the lexicographical order is also well-ordered. In mathematics, a well-order (or well-ordering) 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. ...

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'. ISO 8601 is an international standard for date and time representations issued by the International Organization for Standardization (ISO). ... In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ...

Case of multiple products

Suppose

${ A_1, A_2, dots, A_n }$

is an n-tuple of sets, with respective total orderings

${ <_1, <_2, cdots, <_n }$

The dictionary ordering

$<^d$

$A_1 times A_2 times cdots times A_n$

is then

$(a_1, a_2, dots, a_n) <^d (b_1,b_2, dots, b_n) iff (exists m > 0) (forall i < m) (a_i = b_i) land (a_m <_m b_m)$

That is, if one of the terms

$a_m <_m b_m$

and all the preceding terms are equal.

Informally,

$a_1$

represents the first letter,

$a_2$

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

$C= A_j times A_{j+1} times cdots times A_k$

represented by

$<^d (C)$

This will satisfy

$a <^d (A_i) a' iff (a <_i a')$

$(a,b) <^d (A_i times B) (a',b') iff a <^d (A_i) a' lor ( a=a' land b <^d (B) b')$

where $B = A_{i+1} times A_{i+2} times cdots times A_n.$

To put it simpler, 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 groups then the result is a non-Archimedean group, because e.g. n(0,1) < (1,0) for all n. In abstract algebra, an ordered group is a group G equipped with a partial order ≤ which is translation-invariant; in other words, ≤ has the property that, for all a, b, and g in G, if a ≤ b then ag ≤ bg and ga ≤ gb. ... In mathematics, the Archimedean property of an ordered algebraic structure, such as a linearly ordered group, and in particular of the real numbers, is the property of having no (non-zero) infinitesimals. ...

If the component sets are ordered vector spaces over R (in particular just R), then the result is also an ordered vector space. A point x in R2 and the set of all y such that xâ‰¤y (in red). ...

Ordering of sequences of various lengths

Given a partially ordered set A, the above considerations allow to define naturally a lexicographical partial order $< d$ 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: In abstract algebra, the free monoid on a set A is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from A, with the binary operation of concatenation. ... Look up tuple in Wiktionary, the free dictionary. ... Concatenation is a standard operation in computer programming languages (a subset of formal language theory). ...

u < d v

$u$ is a prefix of $v$ , or
$u = w a u'$ and $v = w b v'$ , where $w$ is the longest common prefix of $u$ and $v$ , $a$ and $b$ are members of A such that $a < b$ , and $u'$ and $v'$ 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, even though it is on the alphabet A; for instance, if A = {a, b}, the language {aⁿb | 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. Look up prefix in Wiktionary, the free dictionary. ... In computer programming and formal language theory, (and other branches of mathematics), a string is an ordered sequence of symbols. ... In mathematics, a well-order (or well-ordering) 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 shortlex (or radix, or length-plus-lexicographic) order is an ordering for ordered sets of objects, where the sequences are primarily sorted by cardinality (length) 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). In mathematics, a well-order (or well-ordering) 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. ... In mathematics, a total order or linear order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ...

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 Y^X is not a countable set, see also cardinal exponentiation. In mathematics, a countable set is a set with the same cardinality (i. ... Aleph-0, the smallest infinite cardinal In mathematics, cardinal numbers, or cardinals for short, are a generalized kind of number used to denote the size of a set. ...

Alternatively, consider the functions f from an inversely well-ordered X to a well-ordered Y with minimum 0, restricted to those which 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 Y^X. If X and Y are countable then the resulting set is also countable. In the mathematical field of set theory, there are three usual operations on ordinals: addition, multiplication, and (ordinal) exponentiation. ...

Monomials

In algebra it is traditional to order terms in a polynomial, by ordering the monomials in the indeterminates. This is fundamental, in order 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 In elementary mathematics, a term is either a single number or variable, or the product of several numbers and/or variables. ... In mathematics, a polynomial is an expression that is constructed from one or more variables and constants, using only the operations of addition, subtraction, multiplication, and constant positive whole number exponents. ... In mathematics, a monomial (or mononomial) is a particular kind of polynomial, having just one term. ... See: indeterminate (variable) statically indeterminate Division by zero This is a disambiguation page — a navigational aid which lists other pages that might otherwise share the same title. ... The term normal form is used in a variety of contexts. ... A computer algebra system (CAS) is a software program that facilitates symbolic mathematics. ...

X < Y < ...

and also to look at higher terms first, that means ordering

... < X³ < X² < X

and also

X < Y^k for all k.

There is some flexibility in ordering monomials, and this can be exploited in Gröbner basis theory. 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. One can view it as a multivariate, non-linear generalization of: the Euclidean algorithm for computation of univariate greatest common...

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 9 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. The decimal (base ten or occasionally denary) numeral system has ten as its base. ... In mathematics, the recurring decimal 0. ...

Lexicographic order with reversed significance

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 dictionary. A rhyming dictionary is a specialist dictionary designed for use in writing poetry. ...

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

x 2 y z 2 < x y 3 z 2

Alternatively, sorting may be done by the sum of the exponents, downward.

Contents

Motivation and uses var ACE_AR = {Site: '756743', Size: '300250'};