Equivalence of Definitions of Total Ordering
Theorem
The following definitions of the concept of Total Ordering are equivalent:
Definition 1
$\RR$ is a total ordering on $S$ if and only if:
That is, $\RR$ is an ordering with no non-comparable pairs:
- $\forall x, y \in S: x \mathop \RR y \lor y \mathop \RR x$
Definition 2
$\RR$ is a total ordering on $S$ if and only if:
\(\text {(1)}: \quad\) | \(\ds \RR \circ \RR\) | \(\subseteq\) | \(\ds \RR\) | |||||||||||
\(\text {(2)}: \quad\) | \(\ds \RR \cap \RR^{-1}\) | \(\subseteq\) | \(\ds \Delta_S\) | |||||||||||
\(\text {(3)}: \quad\) | \(\ds \RR \cup \RR^{-1}\) | \(=\) | \(\ds S \times S\) |
Proof
Definition 1 implies Definition 2
Let $\RR$ be an ordering which is also connected.
- $\RR \circ \RR = \RR$
- $\RR \cap \RR^{-1} = \Delta_S$
and hence by definition of set equality:
- $(1): \quad \RR \circ \RR \subseteq \RR$
- $(2): \quad \RR \cap \RR^{-1} \subseteq \Delta_S$
By Relation is Connected and Reflexive iff Total, $\RR$ is a total relation.
Thus by Relation is Total iff Union with Inverse is Trivial Relation:
- $(3): \quad \RR \cup \RR^{-1} = S \times S$
Hence $\RR$ is a total ordering by definition 2.
$\Box$
Definition 2 implies Definition 1
Let $\RR$ be a relation which fulfils the conditions:
- $(1): \quad \RR \circ \RR \subseteq \RR$
- $(2): \quad \RR \cap \RR^{-1} \subseteq \Delta_S$
- $(3): \quad \RR \cup \RR^{-1} = S \times S$
By definition of transitive relation, we have from $(1)$ that $\RR$ is transitive.
From Relation is Antisymmetric iff Intersection with Inverse is Coreflexive, it follows from $(2)$ that $\RR$ is an antisymmetric relation.
By Relation is Total iff Union with Inverse is Trivial Relation it follows from $(3)$ that $\RR$ is a total relation.
From Relation is Connected and Reflexive iff Total, $\RR$ is both connected and reflexive.
Hence we have that $\RR$ is:
and hence:
$\blacksquare$
Sources
- 1965: Seth Warner: Modern Algebra ... (previous) ... (next): Chapter $\text {III}$: The Natural Numbers: $\S 14$: Orderings: Exercise $14.27 \ \text {(b)}$