Total order

In mathematics, a total order or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation ${\displaystyle \leq }$ on some set ${\displaystyle X}$, which satisfies the following for all ${\displaystyle a,b}$ and ${\displaystyle c}$ in ${\displaystyle X}$:

1. ${\displaystyle a\leq a}$ (reflexive).
2. If ${\displaystyle a\leq b}$ and ${\displaystyle b\leq c}$ then ${\displaystyle a\leq c}$ (transitive).
3. If ${\displaystyle a\leq b}$ and ${\displaystyle b\leq a}$ then ${\displaystyle a=b}$ (antisymmetric).
4. ${\displaystyle a\leq b}$ or ${\displaystyle b\leq a}$ (strongly connected, formerly called total).

Reflexivity (1.) already follows from connectedness (4.), but is required explicitly by many authors nevertheless, to indicate the kinship to partial orders.[1] Total orders are sometimes also called simple,[2] connex,[3] or full orders.[4]

A set equipped with a total order is a totally ordered set;[5] the terms simply ordered set,[2] linearly ordered set,[3][5] and loset[6][7] are also used. The term chain is sometimes defined as a synonym of totally ordered set,[5] but refers generally to some sort of totally ordered subsets of a given partially ordered set.

An extension of a given partial order to a total order is called a linear extension of that partial order.