Lexicographic Orders

The lexicographic order is an order on the Cartesian product of two or more partially ordered sets. The lexicographic order is also known as lexicographical order, alphabetical order, or dictionary order.

Order Involving Two Sets

Let (A, ≼₁) and (B, ≼₂) be two partially ordered sets. The lexicographic order ≼ on the Cartesian product A × B is defined by

\[\left( {a,b} \right) \preccurlyeq \left( {c,d} \right)\]

if and only if

\[a {\,\prec}_1\, c \;\;\text{or}\; \left({a = c \;\;\text{and}\;\; b {\,\preccurlyeq}_2\, d}\right).\]

Order Involving \(N\) Sets

The above definition can be generalized to the Cartesian product of \(n\) posets. Given partially ordered sets \(\left( {{A_1},{\preccurlyeq}_1} \right),\) \(\left( {{A_2},{\preccurlyeq}_2} \right),\ldots\) \(\left( {{A_n},{\preccurlyeq}_n} \right),\) we define the lexicographic order on the Cartesian product \({{A_1} \times {A_2} \times \cdots \times {A_n}}\) as

\[\left( {{a_1},{a_2}, \ldots ,{a_n}} \right) \preccurlyeq \left( {{b_1},{b_2}, \ldots ,{b_n}} \right),\]

where

or there is an integer \(0 \lt i \le n\) such that

where

\[{a_1} = {b_1},\,{a_2} = {b_2},\, \ldots ,\,{a_{i-1}} = {b_{i-1}}\;\;\text{and}\;\;{a_i} {\,\preccurlyeq}_i\, {b_i}.\]

It can be shown that if the sets \({{A_1}, {A_2},\ldots {A_n}}\) are partially ordered, then the lexicographic order is also a partial order. Similarly, the lexicographic order is a total order (well order), if all these sets are totally ordered (well ordered).

Ordering of Words

Suppose now the set \(A\) represents a certain alphabet. The letters \({a_1},{a_2},\ldots,{a_k}\) of the alphabet \(A\) are assumed to be strictly totally ordered:

\[{a_1} \prec {a_2} \prec \cdots \prec {a_k}.\]

The elements of the \(n\text{th}\) Cartesian power \(A^n\) are treated as words or strings of length \(n.\) The order of two words depends on the order of the symbols in the first place where the two words differ (counting from the beginning of the words).

If two words have different lengths, the shorter word is padded with trailing blank characters to have the same length as the longer word. The blank symbol is supposed to come before any other symbol in the alphabet. Then the words can be compared lexicographically.

So, using the basic Latin alphabet, we can sort city names in the following order:

\[\text{Cairo} \preccurlyeq \text{Delhi} \preccurlyeq \text{Jakarta} \preccurlyeq \text{Kinshasa} \preccurlyeq \text{Lagos} \preccurlyeq \text{London} \preccurlyeq \text{Los Angeles} \preccurlyeq \text{Mexico} \preccurlyeq \text{Moscow} \preccurlyeq \text{Mumbai} \preccurlyeq \text{New York} \preccurlyeq \text{Paris} \preccurlyeq \text{Shanghai} \preccurlyeq \text{Tokyo}\]

There is also another convention called shortlex order which is frequently used for comparison of words of different lengths. Under the shortlex word order, a shorter word or string always occurs earlier than a longer word. The shortlex ordering of the city list above looks as follows:

\[\text{Cairo} \preccurlyeq \text{Delhi} \preccurlyeq \text{Lagos} \preccurlyeq \text{Paris} \preccurlyeq \text{Tokyo} \preccurlyeq \text{London} \preccurlyeq \text{Mexico} \preccurlyeq \text{Moscow} \preccurlyeq \text{Mumbai} \preccurlyeq \text{Jakarta} \preccurlyeq \text{Kinshasa} \preccurlyeq \text{New York} \preccurlyeq \text{Shanghai} \preccurlyeq \text{Los Angeles}\]

Ordering of Numeric Tuples

Let \(A = \mathbb{N}.\) The set \(\mathbb{N}^n\) represents \(n-\)tuples of natural numbers - for example, \(\left( {3,1,7} \right)\) for \(n = 3,\) or \(\left( {5,2,4,11,15} \right)\) for \(n = 5.\)

The lexicographic order allows to compare \(n-\)tuples of natural numbers. With the usual "less than" order \(\lt\) on the set of natural numbers \(\mathbb{N},\) we define that

\[\left( {{a_1},{a_2}, \ldots ,{a_n}} \right) \preccurlyeq \left( {{b_1},{b_2}, \ldots ,{b_n}} \right),\]

if there is \(i \le n\) such that \({a_j} = {b_j}\) for all \(j \lt i\) and \({a_i} \le {b_i}.\)

Examples

\[\left( {1,1} \right) \preccurlyeq \left( {1,2} \right);\;\;\;\left( {1,3,2,} \right) \preccurlyeq \left( {1,3,5} \right);\;\;\;\left( {7,5,4,2} \right) \preccurlyeq \left( {7,6,4,2} \right).\]

Similarly we can define lexicographic orders on sets of other numerical objects such as \(\mathbb{Z}^n\) of \(n-\)tuples of integers or \(\mathbb{R}^n\) of \(n-\)tuples of real numbers.

Ordering of Subsets

We can use lexicographic order to sort any objects if they are represented by lists with a partial ordering. Suppose we want to order subsets of a set \(A\) consisting of \(n\) elements. These might be, say, all subsets of the power set of \(A\) or subsets of size \(k\) (\(k-\)subsets).

Recall that the order of elements within a subset does not matter. Therefore, first we should arrange them in increasing order based on the given or implied ordering rule. So, the numbers can be arranged with the standard "less than" ordering, and the letters can be sorted in alphabetical order. Then we can apply lexicographic ordering to the subsets.

For example, the subsets of \(A = \left\{ {a,b,c,d} \right\}\) are represented in lexicographic order as follows:

\[\varnothing \preccurlyeq \left\{ a \right\} \preccurlyeq \left\{ {a,b} \right\} \preccurlyeq \left\{ {a,b,c} \right\} \preccurlyeq \left\{ {a,b,c,d} \right\} \preccurlyeq \left\{ {a,b,d} \right\} \preccurlyeq \left\{ {a,c} \right\} \preccurlyeq \left\{ {a,c,d} \right\} \preccurlyeq \left\{ {a,d} \right\} \preccurlyeq \left\{ b \right\} \preccurlyeq \left\{ {b,c} \right\} \preccurlyeq \left\{ {b,c,d} \right\} \preccurlyeq \left\{ {b,d} \right\} \preccurlyeq \left\{ c \right\} \preccurlyeq \left\{ {c,d} \right\} \preccurlyeq \left\{ d \right\}.\]

See solved problems on Page 2.

Calculus