total orderTotalOrder2001-10-06 16:04:132007-11-04 08:28:54Definitiontotally ordered setlinearly ordered setcomparabilitytotally orderedlinearly orderedchaintotally-ordered setlinearly-ordered settotally-orderedlinearly-orderedtransitivityreflexivityantisymmetrybinary relation\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\PMlinkescapeword{between}
\PMlinkescapeword{equivalent}
\PMlinkescapeword{property}
\PMlinkescapeword{transitive}
\PMlinkescapeword{words}
A \emph{totally ordered set} (or \emph{linearly ordered set}) is a poset $(T,\leq)$ which has the property of \emph{comparability}:
\begin{itemize}
\item for all $x,y\in T$, either $x\leq y$ or $y \leq x$.
\end{itemize}
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$:
\begin{itemize}
\item $x\leq x$. ({\it reflexivity})
\item If $x\leq y$ and $y\leq x$, then $x=y$. ({\it antisymmetry})
\item If $x\leq y$ and $y\leq z$, then $x\leq z$. ({\it transitivity})
\item Either $x\leq y$ or $y \leq x$. ({\it comparability})
\end{itemize}
The binary relation $\leq$ is then called a \emph{total order} or a \emph{linear order} (or \emph{total ordering} or \emph{linear ordering}).
A totally ordered set is also sometimes called a \emph{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 \PMlinkname{well-order}{WellOrderedSet}.
Some people prefer to define the binary relation $<$ as a total order, rather than $\leq$.
In this case, $<$ is required to be \PMlinkname{transitive}{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<y$ or $x=y$).
A totally ordered set can also be defined as a lattice $(T,\lor,\land)$ in which the following property holds:
\begin{itemize}
\item for all $x,y\in T$, either $x\land y=x$ or $x\land y=y$.
\end{itemize}
Then totally ordered sets are \PMlinkname{distributive lattices}{DistributiveLattice}.