Total Orders

Definitions

A partial order relation R defined on a set A does not need to include the set of all ordered pairs (a, b) ∈ A × A. This is why this relation is called partial.

The elements of a partially ordered set (A, R) = (A, ≼) are called comparable if either a ≼ b or b ≼ a. Otherwise, a and b are said to be incomparable. For example, when the elements are ordered by the divisibility relation a | b, the numbers a = 3 and b = 6 of the poset (ℕ, |) 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 lexicographic 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

\[\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\},\left\{ {1,2,3,4} \right\}} \right\}.\]

See solved problems on Page 2.

Calculus