Total Orders on Sets
Recall from the Partial Orders and Strict Partial Orders on Sets page that the relation $R$ on a set $X$ is said to be a partial order on $X$ if $R$ is reflexive, antisymmetric, and transitive. Furthermore, the relation $R$ on a set $X$ is said to be a strict partial order on $X$ if $R$ is irreflexive, antisymmetric, and transitive.
We are about to define total orders on sets, but before we do, we will need to look at a couple of other definitions first.
| Definition: If $X$ is a set and $R$ is a relation on $X$ then if for $x, y \in X$ we have that $x \: R \: y$ or $y \: R \: x$ then $x$ and $y$ are said to be Comparable. If $x \: \not R \: y$ and $y \: \not R \: x$ then $x$ and $y$ are said to be Incomparable. |
For example, consider the set $X = \{0, 1, 2, ... \}$ of nonnegative integers and consider the relation $\mid$ classified such that for all $x, y \in X$ we have that $x \mid y$ says that $x$ divides $y$ or equivalently there exists a nonnegative integer $m$ such that $y = mx$.
This relation is reflexive since for all $x \in X$ we have that $x \mid x$ since for $m = 1$ we get $x = 1 \cdot x$. Furthermore, this relation is antisymmetric since for all $x, y \in X$ we have that $x \mid y$ implies that $x < y$ and so there does not exist an integer $m$ such that $x = my$ so $y \not \mid x$. Lastly, this relation is transitive since for all $x, y, z \in X$ we have that if $x \mid y$ and $y \mid z$ then $x \mid z$ (as you should prove). Thus $R$ is a partial order on $X$.
Now consider the elements $2, 4 \in X$. We have that $2 \mid 4$ and so $2$ and $4$ are comparable. Now consider the elements $2, 7 \in X$. We have that $2 \not \mid 7$ and $7 \not \mid 2$ and so $2$ and $7$ are incomparable. In fact, if $q$ is a prime and $1 < p < q$ then $p$ and $q$ are incomparable. To show this, we note that $q$ is prime and so the only positive divisors of $q$ are $1$. However, $p \neq q$ and $p \neq 1$ so $p \not \mid q$. Furthermore, since $p < q$ there exists no positive integer $m$ such that $q = mp$ and so $q \not \mid p$.
We are now ready to look at a definition of total order on a set $X$.
| Definition: A Total Order on a set $X$ is a relation $R$ on $X$ such that $R$ is a partial order on $X$ and that for all $x, y \in X$ we have that $x$ and $y$ are comparable. A set $X$ is said to be Totally Ordered by $R$ if $R$ is a total order on $X$. |
The example of the divides relation from above is not a total order since we have found incomparable elements in $X$. Instead, consider the set of real numbers $\mathbb{R}$ and the relation $\leq$. We have already seen that this relation is reflexive, antisymmetric, and transitive and so $\leq$ is a partial order on $\mathbb{R}$. Let's now show that $\leq$ is a total order of $R$. Let $x, y \in \mathbb{R}$. There are three cases to consider. First if $x < y$ then $x \leq y$ so $x$ and $y$ are comparable. Secondly, if $x = y$ then $x \leq y$ so $x$ and $y$ are comparable. Lastly, if $x > y$ then $y < x$ and once again, $y$ and $x$ are comparable. In other words, for all $x, y \in \mathbb{R}$ we have that either:
(1)The property above is often called the Trichotomy property and shows that the set of real numbers $\mathbb{R}$ is a totally ordered set with the total order $\leq$.