Calculus

Set Theory

Set Theory Logo

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 \(\require{AMSsymbols}{\left( {{A},{\preccurlyeq}_1} \right)}\) and \(\left( {{B},{\preccurlyeq}_2} \right)\) be two partially ordered sets. The lexicographic order \({\preccurlyeq}\) on the Cartesian product \({{A} \times {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

\[{a_1}{\,\prec}_1\,{b_1},\]

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

\[{{a_1} = {b_1},\,{a_2} = {b_2},\, \ldots ,\,{a_{i-1}} = {b_{i-1}}\;\;}\kern0pt{\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);\;\;\;}\kern0pt{\left( {1,3,2,} \right) \preccurlyeq \left( {1,3,5} \right);\;\;\;}\kern0pt{\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\}.\]


Solved Problems

Click or tap a problem to see the solution.

Example 1

The lexicographic order with the usual “less than” relation is defined on the Cartesian square \(A^2,\) where \(A = \left\{ {1,2,3,4} \right\}.\) Find all pairs in \(A^2\) greater than \(\left({3,2}\right).\)

Example 2

The lexicographic order with the usual “less than” relation is defined on the Cartesian product \(B^3,\) where \(B = \left\{ {1,2,3} \right\}.\) Find all elements in \(B^3\) greater than \(\left({2,1,3}\right)\) and less than \(\left({3,2,1}\right).\)

Example 3

List all \(3-\) subsets of \(\left\{ {a,b,c,d,e} \right\}\) in lexicographic order.

Example 4

List all \(4-\) subsets of \(\left\{ {1,2,3,4,5,6} \right\}\) in lexicographic order.

Example 5

Given two posets \(\left( {A, \le } \right)\) and \(\left( {\mathcal{P}\left( A \right), \subseteq} \right),\) where \(A = \left\{ {1,2,3} \right\}\) and \(\mathcal{P}\left( A \right)\) denotes the power set of \(A.\) The lexicographic order \(\preccurlyeq\) is defined on the Cartesian product \(A \times \mathcal{P}\left( A \right).\) Determine whether the following statements are true or false:
  1. \(\left( {2, \varnothing} \right) \preccurlyeq \left( {1,\left\{ {1,2,3} \right\}} \right)\)
  2. \(\left( {1,\left\{ 1 \right\}} \right) \preccurlyeq \left( {2,\left\{ {2,3} \right\}} \right)\)
  3. \(\left( {2,\left\{ 1 \right\}} \right) \preccurlyeq \left( {2,\left\{ {2,3} \right\}} \right)\)
  4. \(\left( {3,\left\{ 1,3 \right\}} \right) \preccurlyeq \left( {3,\left\{ {2,3} \right\}} \right)\)
  5. \(\left( {3,\left\{ 1,3 \right\}} \right) \preccurlyeq \left( {3,\left\{ {1,2,3} \right\}} \right)\)

Example 6

Given two posets \(\left( {B, \mid } \right)\) and \(\left( {\mathcal{P}\left( B \right), \subseteq} \right),\) where \(B = \left\{ {2,3,4,8} \right\},\) “|” means the divisibility relation, and \(\mathcal{P}\left( B \right)\) denotes the power set of \(B.\) The lexicographic order \(\preccurlyeq\) is defined on the Cartesian product \(B \times \mathcal{P}\left( B \right).\) Determine whether the following statements are true or false:
  1. \(\left( {2, \varnothing} \right) \preccurlyeq \left( {3,\left\{ {4,8} \right\}} \right)\)
  2. \(\left( {2,\left\{ 4 \right\}} \right) \preccurlyeq \left( {4,\left\{ {3,8} \right\}} \right)\)
  3. \(\left( {2,\left\{ 4 \right\}} \right) \preccurlyeq \left( {2,\left\{ {3,4,8} \right\}} \right)\)
  4. \(\left( {4,\left\{ 2,3 \right\}} \right) \preccurlyeq \left( {4,\left\{ {3,4} \right\}} \right)\)
  5. \(\left( {8,\left\{ 1,3 \right\}} \right) \preccurlyeq \left( {4,\left\{ {1,2,3} \right\}} \right)\)

Example 1.

The lexicographic order with the usual “less than” relation is defined on the Cartesian square \(A^2,\) where \(A = \left\{ {1,2,3,4} \right\}.\) Find all pairs in \(A^2\) greater than \(\left({3,2}\right).\)

Solution.

The lexicographic order on \(A^2\) is given by

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

Hence, the following pairs are greater than \(\left({3,2}\right):\)

\[\left( {3,3} \right),\left( {3,4} \right),\left( {4,1} \right),\left( {4,2} \right),\left( {4,3} \right),\left( {4,4} \right).\]

Example 2.

The lexicographic order with the usual “less than” relation is defined on the Cartesian product \(B^3,\) where \(B = \left\{ {1,2,3} \right\}.\) Find all elements in \(B^3\) greater than \(\left({2,1,3}\right)\) and less than \(\left({3,2,1}\right).\)

Solution.

We list the elements of \(B^3\) in lexicographical order:

\[\left( {1,1,1} \right) \preccurlyeq \left( {1,1,2} \right) \preccurlyeq \left( {1,1,3} \right) \preccurlyeq \left( {1,2,1} \right) \preccurlyeq \ldots \preccurlyeq \left( {3,2,3} \right) \preccurlyeq \left( {3,3,1} \right) \preccurlyeq \left( {3,3,2} \right) \preccurlyeq \left( {3,3,3} \right).\]

So, the following elements are greater than \(\left({2,1,3}\right)\) and less than \(\left({3,2,1}\right):\)

\[\left( {2,2,1} \right),\left( {2,2,2} \right),\left( {2,2,3} \right),\left( {2,3,1} \right),\left( {2,3,2} \right),\left( {2,3,3} \right),\left( {3,1,1} \right),\left( {3,1,2} \right),\left( {3,1,3} \right).\]

Example 3.

List all \(3-\) subsets of \(\left\{ {a,b,c,d,e} \right\}\) in lexicographic order.

Solution.

The \(3-\)subsets of the set \(\left\{ {a,b,c,d,e} \right\}\) are ordered in the following way:

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

Example 4.

List all \(4-\) subsets of \(\left\{ {1,2,3,4,5,6} \right\}\) in lexicographic order.

Solution.

All \(4-\)subsets of the set \(\left\{ {1,2,3,4,5,6} \right\}\) are represented in the following order:

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

Example 5.

Given two posets \(\left( {A, \le } \right)\) and \(\left( {\mathcal{P}\left( A \right), \subseteq} \right),\) where \(A = \left\{ {1,2,3} \right\}\) and \(\mathcal{P}\left( A \right)\) denotes the power set of \(A.\) The lexicographic order \(\preccurlyeq\) is defined on the Cartesian product \(A \times \mathcal{P}\left( A \right).\) Determine whether the following statements are true or false:
  1. \(\left( {2, \varnothing} \right) \preccurlyeq \left( {1,\left\{ {1,2,3} \right\}} \right)\)
  2. \(\left( {1,\left\{ 1 \right\}} \right) \preccurlyeq \left( {2,\left\{ {2,3} \right\}} \right)\)
  3. \(\left( {2,\left\{ 1 \right\}} \right) \preccurlyeq \left( {2,\left\{ {2,3} \right\}} \right)\)
  4. \(\left( {3,\left\{ 1,3 \right\}} \right) \preccurlyeq \left( {3,\left\{ {2,3} \right\}} \right)\)
  5. \(\left( {3,\left\{ 1,3 \right\}} \right) \preccurlyeq \left( {3,\left\{ {1,2,3} \right\}} \right)\)

Solution.

  1. The statement \(\left( {2, \varnothing} \right) \preccurlyeq \left( {1,\left\{ {1,2,3} \right\}} \right)\) is false because \(2 \not\le 1.\)
  2. The statement \(\left( {1,\left\{ 1 \right\}} \right) \preccurlyeq \left( {2,\left\{ {2,3} \right\}} \right)\) is true since \(1 \le 2.\)
  3. The statement \(\left( {2,\left\{ 1 \right\}} \right) \preccurlyeq \left( {2,\left\{ {2,3} \right\}} \right)\) is false since \(\left\{ {1} \right\} \not\subseteq \left\{ {2,3} \right\}.\)
  4. Similarly to the previous case, the statement \(\left( {3,\left\{ 1,3 \right\}} \right) \preccurlyeq \left( {3,\left\{ {2,3} \right\}} \right)\) is false because \(\left\{ {1,3} \right\} \not\subseteq \left\{ {2,3} \right\}.\)
  5. The statement \(\left( {3,\left\{ 1,3 \right\}} \right) \preccurlyeq \left( {3,\left\{ {1,2,3} \right\}} \right)\) is true since \(3 = 3\) and \(\left\{ {1,3} \right\} \subseteq \left\{ {1,2,3} \right\}.\)

Example 6.

Given two posets \(\left( {B, \mid } \right)\) and \(\left( {\mathcal{P}\left( B \right), \subseteq} \right),\) where \(B = \left\{ {2,3,4,8} \right\},\) “|” means the divisibility relation, and \(\mathcal{P}\left( B \right)\) denotes the power set of \(B.\) The lexicographic order \(\preccurlyeq\) is defined on the Cartesian product \(B \times \mathcal{P}\left( B \right).\) Determine whether the following statements are true or false:
  1. \(\left( {2, \varnothing} \right) \preccurlyeq \left( {3,\left\{ {4,8} \right\}} \right)\)
  2. \(\left( {2,\left\{ 4 \right\}} \right) \preccurlyeq \left( {4,\left\{ {3,8} \right\}} \right)\)
  3. \(\left( {2,\left\{ 4 \right\}} \right) \preccurlyeq \left( {2,\left\{ {3,4,8} \right\}} \right)\)
  4. \(\left( {4,\left\{ 2,3 \right\}} \right) \preccurlyeq \left( {4,\left\{ {3,4} \right\}} \right)\)
  5. \(\left( {8,\left\{ 1,3 \right\}} \right) \preccurlyeq \left( {4,\left\{ {1,2,3} \right\}} \right)\)

Solution.

  1. The statement \(\left( {2, \varnothing} \right) \preccurlyeq \left( {3,\left\{ {4,8} \right\}} \right)\) is false because \(2\) does not divide \(3.\)
  2. The statement \(\left( {2,\left\{ 4 \right\}} \right) \preccurlyeq \left( {4,\left\{ {3,8} \right\}} \right)\) is true since \(2\) divides \(4\) (although \(\left\{ {4} \right\} \not\subseteq \left\{ {3,8} \right\}\)).
  3. The statement \(\left( {2,\left\{ 4 \right\}} \right) \preccurlyeq \left( {2,\left\{ {3,4,8} \right\}} \right)\) is true because \(2 = 2\) and \(\left\{ {4} \right\} \subseteq \left\{ {3,4,8} \right\}.\)
  4. The statement \(\left( {4,\left\{ 2,3 \right\}} \right) \preccurlyeq \left( {4,\left\{ {3,4} \right\}} \right)\) is false. Here \(4 = 4,\) but\(\left\{ {2,3} \right\} \not\subseteq \left\{ {3,4} \right\}.\)
  5. The statement \(\left( {8,\left\{ 1,3 \right\}} \right) \preccurlyeq \left( {4,\left\{ {1,2,3} \right\}} \right)\) is false since \(8\) does not divide \(4.\)