# 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].$