Calculus

Set Theory

Set Theory Logo

Total Orders

Definitions

A partial order relation \(R\) defined on a set \(A\) does not need to include the set of all ordered pairs \(\left( {a,b} \right) \in A \times A.\) This is why this relation is called partial.

The elements of a partially ordered set \(\require{AMSsymbols}{\left( {A,R} \right) = \left( {A, \preccurlyeq} \right)}\) are called comparable if either \(a \preccurlyeq b\) or \(b \preccurlyeq a.\) Otherwise, \(a\) and \(b\) are said to be incomparable. For example, when the elements are ordered by the divisibility relation \(a \mid b,\) the numbers \(a = 3\) and \(b = 6\) of the poset \(\left( {\mathbb{N},\mid} \right)\) are comparable, but \(a = 3\) and \(b = 5\) are incomparable.

A partially ordered set \(\left( {A, \preccurlyeq} \right)\) in which any two elements are comparable is called a total order. Total orders are also sometimes called linear orders.

Formally, a binary relation \(R\) on a non-empty set \(A\) is a total order if the relation is

  • connex
  • antisymmetric, and
  • transitive.

The connex property makes all pairs of elements comparable, so we have either \(a \preccurlyeq b\) or \(b \preccurlyeq a\) for all \(a,b \in A.\) The connex property implies reflexivity since \(a \preccurlyeq a.\) To convert a partial order into a total order, we need to replace the reflexivity property by the stronger connexity property. Hence, we can consider a total order as a special case of a partial order.

Examples of Total Orders

Alphabetical Order

Alphabetical order (also known as dictionary order or lexicographical order) is sorting words or strings created from a certain alphabet. The letters \({a_1},{a_2}, \ldots ,{a_n}\) of the alphabet \(A\) are assumed to be strictly totally ordered:

\[{a_1} \prec {a_2} \prec \cdots \prec {a_n}.\]

The order of two words or strings depends on the first symbol on the alphabetical order of the symbols in the first place (counting from the beginning of the words) where the two words differ. So, using the basic Latin alphabet, we can arrange names in the following order:

\[\text{Donna} \preccurlyeq \text{Jim} \preccurlyeq \text{Jill} \preccurlyeq \text{Kendra} \preccurlyeq \text{Kenn} \preccurlyeq \text{Mark} \preccurlyeq \text{Michael} \preccurlyeq \text{Michelle} \preccurlyeq \text{Rebecca} \preccurlyeq \text{Teresa}\]

Similarly, sorting based on \(7\text{-bit}\) ASCII character code may look as follows:

\[{\text{#}3 \preccurlyeq \text{#}312 \preccurlyeq \left( {45FG} \right) \preccurlyeq \text{CALCULUS} \preccurlyeq \text{CALCulus} \preccurlyeq \text{calcULUS}}\]

Ordering on the Set of Real Numbers \(\mathbb{R}\)

The set of real numbers \(\mathbb{R}\) ordered by the usual “less than or equal to” \(\left( \le \right)\) or “greater than or equal to” \(\left( \ge \right)\) relations is totally ordered. This is also true for any subsets of integers and rational numbers.

Divisibility Relation on Certain Sets

The divisibility relation on the set of natural numbers \(\mathbb{N}\) is a partial order and not a total order. However certain subsets of \(\mathbb{N}\) with the divisibility relation on them may be totally ordered. For instance, consider the divisibility relation on the subset

\[A = \left\{ {3,9,27,81} \right\}.\]

As it can be seen, all ordered pairs in the relation are comparable.

Chains

A set that is partially ordered but not totally ordered may have subsets (like in the divisibility relation above) that are totally ordered. Such subsets are called chains.

The length \(\ell\) of a finite chain \(C\) is one less than the number of elements in the chain:

\[\ell\left( C \right) = \left| C \right| – 1.\]

For example, the power set \(\mathcal{P}\left( {\left\{ {1,2,3,4} \right\}} \right)\) is partially ordered with respect to the subset relation. Since

\[\require{AMSsymbols}{\varnothing \subseteq \left\{ 1 \right\} \subseteq \left\{ {1,2} \right\} \subseteq \left\{ {1,2,3} \right\} \subseteq \left\{ {1,2,3,4} \right\},}\]

the poset \(\left( {\mathcal{P}\left( {\left\{ {1,2,3,4} \right\}} \right), \subseteq} \right)\) has the chain \(C\) of length \(4:\)

\[{C = \left\{ {\varnothing,\left\{ 1 \right\},\left\{ {1,2} \right\},\left\{ {1,2,3} \right\},}\right.}\kern0pt{\left.{\left\{ {1,2,3,4} \right\}} \right\}.}\]


Solved Problems

Click or tap a problem to see the solution.

Example 1

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

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.

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.\) \(\kern-4pt\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.\) \(\kern-4pt\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.\) \(\kern-4pt\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),\left( {1,4} \right),}\right.}\kern0pt{\left.{\left( {1,5} \right),\left( {2,2} \right),}\right.}\kern0pt{\left.{\left( {2,4} \right),\left( {3,3} \right),}\right.}\kern0pt{\left.{\left( {3,5} \right),\left( {4,4} \right),}\right.}\kern0pt{\left.{\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,\;\;}\kern0pt{a \preccurlyeq c \preccurlyeq b,\;\;}\kern0pt{b \preccurlyeq a \preccurlyeq c,\;\;}\kern0pt{b \preccurlyeq c \preccurlyeq a,\;\;}\kern0pt{c \preccurlyeq a \preccurlyeq b,\;\;}\kern0pt{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,}\right.}\kern0pt{\left.{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\},\;\;}\kern0pt{{C_2} = \left\{ {1,5,10,20,60} \right\},\;\;}\kern0pt{{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.\) \(\kern-4pt\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.\) \(\kern-4pt\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.\) \(\kern-4pt\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),\left( {1,4} \right),}\right.}\kern0pt{\left.{\left( {1,5} \right),\left( {2,2} \right),}\right.}\kern0pt{\left.{\left( {2,4} \right),\left( {3,3} \right),}\right.}\kern0pt{\left.{\left( {3,5} \right),\left( {4,4} \right),}\right.}\kern0pt{\left.{\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),}\right.}\kern0pt{\left.{\left( {1,4} \right),\left( {1,5} \right),}\right.}\kern0pt{\left.{\left( {2,2} \right),\left( \color{red}{2,3} \right),}\right.}\kern0pt{\left.{\left( {2,4} \right),\left( \color{red}{2,5} \right),}\right.}\kern0pt{\left.{\left( {3,3} \right),\left( \color{red}{3,4} \right),}\right.}\kern0pt{\left.{\left( {3,5} \right),\left( {4,4} \right),}\right.}\kern0pt{\left.{\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].\]