Total order

related topics
{math, number, function}
{rate, high, increase}

In set theory, a total order, linear order, simple order, or (non-strict) ordering is a binary relation (here denoted by infix ) on some set X. The relation is transitive, antisymmetric, and total. A set paired with a total order is called a totally ordered set, a linearly ordered set, a simply ordered set, or a chain.

If X is totally ordered under ≤, then the following statements hold for all a, b and c in X:

Contrast with a partial order, which has a weaker form of the third condition (it only requires reflexivity, not totality). A relation having the property of "totality" means that any pair of elements in the set of the relation are mutually comparable under the relation.

Totality implies reflexivity, that is, aa. Thus a total order is also a partial order, that is, a binary relation which is reflexive, antisymmetric and transitive (and also satisfying the "totality" condition). An extension of a given partial order to a total order is called a linear extension of that partial order.


Strict total order

For each (non-strict) total order ≤ there is an associated asymmetric (hence irreflexive) relation <, called a strict total order, which can equivalently be defined in two ways:


  • The relation is transitive: a < b and b < c implies a < c.
  • The relation is trichotomous: exactly one of a < b, b < a and a = b is true.
  • The relation is a strict weak order, where the associated equivalence is equality.

Full article ▸

related documents
Analytic continuation
Partial derivative
Transcendental number
Uniform convergence
Burnside's problem
Tangent space
Analytic function
Sufficiency (statistics)
Symmetric matrix
Polymorphism in object-oriented programming
Root-finding algorithm
Planar graph
Binary heap
Additive category
Tree automaton
Hausdorff space
Binary tree
Euler–Maclaurin formula
Spectral theorem
Bubble sort
Shell sort
Brouwer fixed point theorem
Self-organizing map
Naive Bayes classifier