$\begingroup$

What is the difference between total order and total relation?

$\endgroup$

3 Answers

$\begingroup$

A total order relation is a total relation that is also transitive and anti-symmetric.

Therefore the difference is we dropped the requirements of transitivity and anti-symmetry.

---

Formally for any binary relation $R$ on $X$ we have in the language of relation algebra:

$$R\text{ is a total order on }X\iff (R\cup R^{-1}=X\times X)\land (R\circ R\subseteq R)\land (R\cap R^{-1}=\text{id}_X)$$ $$R\text{ is total on }X\iff (R\cup R^{-1}=X\times X)$$

$\endgroup$ $\begingroup$

Every total order is a total relation.

However a total relation need not be a total order.

For example, let $S = \{1,2\}$, and consider the relation $R$ on $S$ given by $$R = \{(1,1),(1,2),(2,1),(2,2)\}$$ Clearly, $R$ is a total relation on $S$.

But $R$ is not anti-symmmetric, since $1\,R\,2$ and $2\,R\,1$, but $1 \ne 2$.

$\endgroup$ $\begingroup$

Just read the first sentence of each link you provided:

In mathematics, a binary relation R over a set X is total or complete if for all a and b in X, a is related to b or b is related to a (or both).

and compare it to:

In mathematics, a linear order, total order, simple order, or (non-strict) ordering is a binary relation on some set $X$, which is antisymmetric, transitive, and total

---

In other words, a total order is a total relation with additional properties, meaning every total order is a total relation, but not every total relation is a total order.

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy