Lexicographical order

In mathematics, the lexicographical order, or dictionary order, is a natural order structure of the cartesian product of two ordered sets. Given A and B, two ordered sets, the lexicographical order in the cartesian product A × B is defined as

Related Topics:
Mathematics - Order - Cartesian product

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:(a,b) ≤ (a′,b′) if and only if a < a′, or a = a′ and b ≤ b′.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The name comes from its generalizing the order given to words in a dictionary: a sequence of letters (i.e. 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. 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 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.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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

Related Topics:
ISO 8601 - Computerized sorting

~ ~ ~ ~ ~ ~ ~ ~ ~ ~