# 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: