Lexicographical order

The lexicographic ordering is a method to obtain from a linear order for simple objects, such as alphabetically arranged letters, a linear order for composite objects, composed for example of letter words. The eponymous example is the arrangement of words in a lexicon: they are first sorted by their initial letters, then the words with the same first letter after each second letter, etc. If a word is very in a different initial part included ( such as "valley" in "Talent " ), so the shorter word is listed first.

Definition and Examples

Formally, this order can be described as follows: A string is smaller than a string (that is, lies in the sorting ago) when

• Either the first character of, in which the two strings differ, is smaller than the corresponding character of,
• Or if the beginning of forms, but is shorter.

A special case of this order is the lexicographic ordering of finite sequences of a fixed length. For example, an ordered pair is lexicographically smaller than a pair if

• Either
• Or and

Applies.

An example of such an order is the chronological order of number triples (year, month, day): A date X is earlier than another date Y, if

• Either the date of X is less than the annual number of Y
• Or the annual figures are the same, but X is in an earlier during the year month
• Or the dates and months are the same, but the day of X is less than the day of Y.

Another example is the usual order within a medal table, with the first criterion, the number of gold medals is crucial, with the same gold medal count the number of silver medals and then again to tie the number of bronze medals:

Mathematical use

Infinite sequences

Analogously, the lexicographic order defined on infinite sequences: a sequence is lexicographically smaller than a consequence but when both sequences before a given index k are equal. Take, for example the sequence numbers of the members, it can be interpreted as a decimal fraction of the result, which is a real number between and. The lexicographic ordering of sequences substantially corresponds to the natural order of real numbers. You must attend only note that a decimal fraction, which eventually assumes Only digit lexicographic has an immediate successor, who represents the same real number. (eg )

Further generalization

The principle may be extended to sequences in which the index area is an arbitrary well-ordered set. In this case, defined functions ( being linearly ordered ), if the minimum element of the domain, and for the different applies. The resulting order of the functions is again linearly ordered.

Application: chains in the power set of an ordinal

In set theory, the special case is often considered, in which the index set is an ordinal number and the sequence members only assume the values ​​or. This basic set is denoted by and it is in a bijective relationship to the power set of. An ordinal is always seen as the set of its predecessors ordinals. One subset of can be assigned to the function for which, if and when. Conversely, it comes from a function with the amount back to a subset of the. We now consider the lexicographical order, as defined above. This linear order can be used for combinatorial questions about infinite cardinal numbers. The following applies:

Application in Microeconomics

→ See also: preference relation

Is given by with the bundle of goods / the alternative and the alternative (accordingly, for example, the amount of good 2 in the bundle of goods ). It refers to a preference - indifference relation R as lexicographically if if and only if either or and at the same time. In other words, a bundle of goods is only relative to a second preferred weak at a lexicographical preference - indifference relation ( that is as least as good as this one viewed ), if it contains more units from the first Good or alternatively, if both goods bundles the same number of units include of this right, if it contains more units of the second good.

Properties of the lexicographic order of preference: