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, a ≤ a. 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 ▸