Total order

In mathematics, a total 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).

Total orders are sometimes also called simple,[1] connex,[2] or full orders.[3]

A set equipped with a total order is a totally ordered set;[4] the terms simply ordered set,[1] linearly ordered set,[2][4] and loset[5][6] are also used. The term chain is sometimes defined as a synonym of totally ordered set,[4] 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.