Calculus

Set Theory

Set Theory Logo

Lexicographic Orders

Solved Problems

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.\)
Page 1 Page 2