# 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$. ()

• 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 (http://planetmath.org/WellOrderedSet).

Some people prefer to define the binary relation $<$ as a total order, rather than $\leq$. In this case, $<$ is required to be transitive (http://planetmath.org/Transitive3) 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 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 (http://planetmath.org/DistributiveLattice).

 Title total order Canonical name TotalOrder Date of creation 2013-03-22 11:43:35 Last modified on 2013-03-22 11:43:35 Owner yark (2760) Last modified by yark (2760) Numerical id 25 Author yark (2760) Entry type Definition Classification msc 06A05 Classification msc 91B12 Classification msc 55-00 Classification msc 55-01 Synonym linear order Synonym total ordering Synonym linear ordering Related topic PartialOrder Related topic Relation Related topic SortingProblem Related topic OrderedRing Related topic ProofOfGeneralizedIntermediateValueTheorem Related topic LinearContinuum Defines totally ordered set Defines linearly ordered set Defines comparability Defines totally ordered Defines linearly ordered Defines chain Defines totally-ordered set Defines linearly-ordered set Defines totally-ordered Defines linearly-ordered