Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

Section 19.4 Total orders

comparable elements
elements \(a,b\) in a partially ordered set such that either \(a \partorder b\) or \(b \partorder a\)
incomparable elements
elements that are not comparable

Example 19.4.1. Comparable and incomparable subsets.

Let \(U\) represent some universal set containing at least two elements, and consider \(\powset{U}\) partially ordered by \(\mathord{\subseteq}\text{.}\)
  • Both the empty set \(\emptyset\) and the universal set \(U\) are comparable to every element of \(\powset{U}\text{.}\)
  • For \(x,y\in U\) with \(x\ne y\text{,}\) then \(\{x\},\{y\}\) are incomparable.
  • In fact, for every non-empty, proper subset \(A \subsetneqq U\) there exists a subset \(B \subseteq U\) which is incomparable to \(A\text{:}\) take \(B = \cmplmnt{A}\text{.}\)
However, do not let the second two points above lead you astray: it is not necessary for subsets to be disjoint in order to be incomparable. As long as each of a pair of subsets contains an element that the other doesn’t, then the two will be incomparable by \(\mathord{\subseteq}\text{.}\)
total order
a partial order on a set such that every pair of elements is comparable
totally ordered set
a set equipped with a total order

Example 19.4.2. Subset order is not total.

For universal set \(U\text{,}\) order \(\mathord{\subseteq}\) on \(\powset{U}\) is not total except when \(\card{U} \le 1\text{.}\)

Example 19.4.3. Usual order of numbers is total.

Our usual order for numbers, \(\mathord{\leq}\text{,}\) is a total order on \(\N\text{,}\) on \(\Z\text{,}\) on \(\Q\text{,}\) or on \(\R\text{.}\)

Example 19.4.4. Total order on alphabet induces total order on words.

If \(\mathord{\partorder}\) is a total order on an alphabet \(\Sigma\text{,}\) then the lexicographic order \(\words{\partorder}\) described in Example 19.2.7 is a total order on the set of words \(\words{\Sigma}\text{.}\)

Example 19.4.5. Pulling back a total order through an injection.

If \(B\) is totally ordered and we use an injection \(\ifuncdef{f}{A}{B}\) to “pull back” the order on \(B\) to an order on \(A\) (see Example 19.2.11), then the newly created order on \(A\) will also be total.

Example 19.4.6. Countable can be totally ordered.

If \(A\) is a countably infinite set, then there exists a bijection \(\funcdef{f}{\N}{A}\text{.}\) We can use the inverse \(\funcdef{\inv{f}}{A}{\N}\) to “pull back” the usual total order \(\mathord{\le}\) on \(\N\) to a total order on \(A\) (see Example 19.4.5).
Another point of view on this is that our bijection \(f\) creates an infinite sequence
\begin{equation*} a_0, a_1, a_2, \dotsc \text{,} \end{equation*}
where each element of \(A\) appears exactly once. This sequence can be turned into a specification of the total order on \(A\) by just turning the commas into \(\mathord{\le}\) symbols:
\begin{equation*} a_0 \le a_1 \le a_2 \le \dotsb \text{.} \end{equation*}

Remark 19.4.7.

The pattern of Example 19.4.6 becomes even simpler when we apply it to a finite set: a total order on a finite set is no different than an ordering of the set elements into a list, as
\begin{equation*} a_0, a_1, a_2, \dotsc, a_n \end{equation*}
can simply be turned into
\begin{equation*} a_0 \le a_1 \le a_2 \le \dotsb \le a_n \text{,} \end{equation*}
and vice versa.

Question 19.4.8.

If \(A\) is a finite, totally ordered set, what does the corresponding Hasse diagram look like?
The answer to this question is contained in Remark 19.4.7.

Example 19.4.10. A totally ordered finite set.

Figure 19.4.11 exhibits the Hasse diagram for the total order \(\mathord{\mid}\) on the set \(\{2,4,8,16,32\}\text{,}\) though we have drawn the diagram on a slant from the vertical to be make it easier to see the entire diagram at a glance.
A Hasse diagram of a totally ordered set.
Figure 19.4.11. A Hasse diagram of a totally ordered set.
<Prev^TopNext>