Calculus

Set Theory

Set Theory Logo

Total Orders

Solved Problems

Click or tap a problem to see the solution.

Example 1

List all total orders on the set A = {a, b, c}.

Example 2

Let A be the set of natural numbers which are divisors of 60. Find a chain of length 4 in the poset (A, |), where | represents the divisibility relation.

Example 3

Determine which of the following subset relations are total orders.

  1. \(\left( {\left\{ {\varnothing,\left\{ a \right\},\left\{ {b,a} \right\},\left\{ {d,a,b} \right\},} \right.} \right.\) \(\left. {\left. {\left\{ {f,d,b,a} \right\}} \right\}, \subseteq } \right)\)
  2. \(\left( {\left\{ {\varnothing,\left\{ k \right\},\left\{ {k,\ell} \right\},\left\{ {k,m} \right\},} \right.} \right.\) \(\left. {\left. {\left\{ {k,\ell,m,n} \right\}} \right\}, \subseteq } \right)\)
  3. \(\left( {\left\{ {\left\{ {p,r,s,t} \right\},\left\{ {s,p} \right\},\left\{ {t,p,s} \right\},} \right.} \right.\) \(\left. {\left. {\left\{ p \right\}} \right\}, \subseteq } \right)\)

Example 4

The relation \(R\) on the set \(A = \left\{ {1,2,3,4,5} \right\}\) is given by \(R = \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {1,3} \right),}\right.\) \(\left( {1,4} \right),\left( {1,5} \right),\left( {2,2} \right),\) \(\left( {2,4} \right),\left( {3,3} \right),\left( {3,5} \right),\) \(\left.{\left( {4,4} \right),\left( {5,5} \right)} \right\}.\) Determine a minimum augmentation relation \(S\) such that \(R \cup S\) is a total order.

Example 1.

List all total orders on the set \(A = \left\{ {a,b,c} \right\}.\)

Solution.

A total order on a set must include all elements of the set. In the given case, we need to list all ordered triples. So we have the following total orders:

\[a \preccurlyeq b \preccurlyeq c,\;\;a \preccurlyeq c \preccurlyeq b,\;\;b \preccurlyeq a \preccurlyeq c,\;\;b \preccurlyeq c \preccurlyeq a,\;\;c \preccurlyeq a \preccurlyeq b,\;\;c \preccurlyeq b \preccurlyeq a.\]

As it can be seen, there are \(6\) different total orders, which is equal to the number of permutations on the set of \(3\) elements:

\[3! = 6.\]

The number of total orders on a set of \(n\) elements is equal to \(n!\)

Example 2.

Let \(A\) be the set of natural numbers which are divisors of \(60.\) Find a chain of length \(4\) in the poset \(\left( {A, \mid} \right),\) where \(\mid\) represents the divisibility relation.

Solution.

The prime factorization of the number \(60\) has the form:

\[60 = {2^2} \times 3 \times 5,\]

so divisors of \(60\) are represented by the following set:

\[A = \left\{ {1,2,3,4,5,6,10,12,15,20,30,60} \right\}.\]

The poset \(\left( {A, \mid} \right),\) contains several chains of length \(4\) some of them are listed below:

\[{C_1} = \left\{ {1,2,4,12,60} \right\},\;\;{C_2} = \left\{ {1,5,10,20,60} \right\},\;\;{C_3} = \left\{ {1,3,6,12,60} \right\}.\]

Example 3.

Determine which of the following subset relations are total orders.

  1. \(\left( {\left\{ {\varnothing,\left\{ a \right\},\left\{ {b,a} \right\},\left\{ {d,a,b} \right\},} \right.} \right.\) \(\left. {\left. {\left\{ {f,d,b,a} \right\}} \right\}, \subseteq } \right)\)
  2. \(\left( {\left\{ {\varnothing,\left\{ k \right\},\left\{ {k,\ell} \right\},\left\{ {k,m} \right\},} \right.} \right.\) \(\left. {\left. {\left\{ {k,\ell,m,n} \right\}} \right\}, \subseteq } \right)\)
  3. \(\left( {\left\{ {\left\{ {p,r,s,t} \right\},\left\{ {s,p} \right\},\left\{ {t,p,s} \right\},} \right.} \right.\) \(\left. {\left. {\left\{ p \right\}} \right\}, \subseteq } \right)\)

Solution.

  1. The subset relation on this set is a total order since
    \[\varnothing \subseteq \left\{ a \right\} \subseteq \left\{ {b,a} \right\} \subseteq \left\{ {d,a,b} \right\} \subseteq \left\{ {f,d,b,a} \right\}.\]
  2. The subset relation on this set is not a total order because the elements \({\left\{ {k,\ell} \right\}}\) and \({\left\{ {k,m} \right\}}\) are not comparable:
    \[\left\{ {k,\ell} \right\} \not\subseteq \left\{ {k,m} \right\}\text{ and } \left\{ {k,m} \right\} \not\subseteq \left\{ {k,\ell} \right\}.\]
  3. Here we have a total order since all elements of the set can be ordered using the subset relation:
    \[\left\{ p \right\} \subseteq \left\{ {s,p} \right\} \subseteq \left\{ {t,p,s} \right\} \subseteq \left\{ {p,r,s,t} \right\}.\]

Example 4.

The relation \(R\) on the set \(A = \left\{ {1,2,3,4,5} \right\}\) is given by \(R = \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {1,3} \right),}\right.\) \(\left( {1,4} \right),\left( {1,5} \right),\left( {2,2} \right),\) \(\left( {2,4} \right),\left( {3,3} \right),\left( {3,5} \right),\) \(\left.{\left( {4,4} \right),\left( {5,5} \right)} \right\}.\) Determine a minimum augmentation relation \(S\) such that \(R \cup S\) is a total order.

Solution.

To construct a total order on \(A\) we need to make all elements of the set \(A\) comparable:

\[1 \preccurlyeq 2 \preccurlyeq 3 \preccurlyeq 4 \preccurlyeq 5.\]

We're lacking in \(R\) the following pairs:

\[S = \left\{ {\left( \color{red}{2,3} \right),\left( \color{red}{2,5} \right),\left( \color{red}{3,4} \right),\left( \color{red}{4,5} \right)} \right\}.\]

So, the total order relation \(R \cup S\) is given by

\[R \cup S = \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {1,3} \right),\left( {1,4} \right),\left( {1,5} \right),\left( {2,2} \right),\left( \color{red}{2,3} \right),\left( {2,4} \right),\left( \color{red}{2,5} \right),\left( {3,3} \right),\left( \color{red}{3,4} \right),\left( {3,5} \right),\left( {4,4} \right),\left( \color{red}{4,5} \right),\left( {5,5} \right)} \right\}.\]

The relation \(R \cup S\) is represented by the upper triangular matrix:

\[{M_{R \cup S}} = \left[ {\begin{array}{*{20}{c}} 1&1&1&1&1\\ 0&1&\color{red}{1}&1&\color{red}{1}\\ 0&0&1&\color{red}{1}&1\\ 0&0&0&1&\color{red}{1}\\ 0&0&0&0&1 \end{array}} \right].\]
Page 1 Page 2