Total order

In mathematics, a total order, simple order, linear order, connex order, or full order is a binary relation on some set X {displaystyle X} , which is antisymmetric, transitive, and a connex relation. A set paired with a total order is called a chain, a totally ordered set, a simply ordered set, or a linearly ordered set. Formally, a binary relation ≤ {displaystyle leq } is a total order on a set X {displaystyle X} if the following statements hold for all a , b {displaystyle a,b} and c {displaystyle c} in X {displaystyle X} : Antisymmetry eliminates uncertain cases when both a {displaystyle a} precedes b {displaystyle b} and b {displaystyle b} precedes a {displaystyle a} .:325 A relation having the connex property means that any pair of elements in the set of the relation are comparable under the relation. This also means that the set can be diagrammed as a line of elements, giving it the name linear.:330 The connex property also implies reflexivity, i.e., a ≤ a. Therefore, a total order is also a (special case of a) partial order, as, for a partial order, the connex property is replaced by the weaker reflexivity property. An extension of a given partial order to a total order is called a linear extension of that partial order. For each (non-strict) total order ≤ there is an associated asymmetric (hence irreflexive) transitive semiconnex relation <, called a strict total order or strict semiconnex order, which can be defined in two equivalent ways: