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 (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<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 (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