total order


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

  • for all x,yT, either xy or yx.

In other words, a totally ordered set is a set T with a binary relationMathworldPlanetmath on it such that the following hold for all x,y,zT:

  • xx. (reflexivityMathworldPlanetmath)

  • If xy and yx, then x=y. (antisymmetry)

  • If xy and yz, then xz. (transitivity)

  • Either xy or yx. (comparability)

The binary relation 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 . In this case, < is required to be transitiveMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath (http://planetmath.org/Transitive3) and to obey the law of trichotomy. It is straightforward to check that this is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath to the above definition, with the usual relationship between < and (that is, xy if and only if either x<y or x=y).

A totally ordered set can also be defined as a latticeMathworldPlanetmath (T,,) in which the following property holds:

  • for all x,yT, either xy=x or xy=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