Total Orders
Solved Problems
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:
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:
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:
so divisors of \(60\) are represented by the following set:
The poset \(\left( {A, \mid} \right),\) contains several chains of length \(4\) some of them are listed below:
Example 3.
Determine which of the following subset relations are total orders.
- \(\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)\)
- \(\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)\)
- \(\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.
- 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\}.\]
- 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\}.\]
- 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:
We're lacking in \(R\) the following pairs:
So, the total order relation \(R \cup S\) is given by
The relation \(R \cup S\) is represented by the upper triangular matrix: