total order

A totally ordered set (or linearly ordered set) is a poset $(T,\leq)$ which has the property of comparability:

• for all $x,y\in T$ , either $x\leq y$ or $y \leq x$ .

In other words, a totally ordered set is a set $T$ with a binary relation $\leq$ on it such that the following hold for all $x,y,z\in T$ :

• $x\leq x$ . (reflexivity)
• If $x\leq y$ and $y\leq x$ , then $x=y$ . (antisymmetry)
• If $x\leq y$ and $y\leq z$ , then $x\leq z$ . (transitivity)
• Either $x\leq y$ or $y \leq x$ . (comparability)

The binary relation $\leq$ is then called a total order or a linear order (or total ordering or linear ordering). A totally ordered set is also sometimes called a chain, especially when it is considered as a subset of some other poset. If every nonempty subset of $T$ has a least element, then the total order is called a well-order.

Some people prefer to define the binary relation $<$ as a total order, rather than $\leq$ . In this case, $<$ is required to be transitive and to obey the law of trichotomy. It is straightforward to check that this is equivalent to the above definition, with the usual relationship between $<$ and $\leq$ (that is, $x\leq y$ if and only if either $x<y$ or $x=y$ ).

A totally ordered set can also be defined as a lattice $(T,\lor,\land)$ in which the following property holds:

• for all $x,y\in T$ , either $x\land y=x$ or $x\land y=y$ .

Then totally ordered sets are distributive lattices.