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}$:

Requirements 1. to 3. just make up the definition of a partial order. Reflexivity (1.) already follows from strong connectedness (4.), but is required explicitly by many authors nevertheless, to indicate the kinship to partial orders. Total orders are sometimes also called simple, connex, or full orders.

A set equipped with a total order is a totally ordered set; the terms simply ordered set, linearly ordered set, toset and loset are also used. The term chain is sometimes defined as a synonym of totally ordered set, but generally refers to a totally ordered subset 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.

For delimitation purposes, a total order as defined above is sometimes called non-strict order. For each (non-strict) total order ${\displaystyle \leq }$ there is an associated relation ${\displaystyle <}$, called the strict total order associated with ${\displaystyle \leq }$ that can be defined in two equivalent ways:

Conversely, the reflexive closure of a strict total order ${\displaystyle <}$ is a (non-strict) total order.

Thus, a strict total order on a set ${\displaystyle X}$ is a strict partial order on ${\displaystyle X}$ in which any two distinct elements are comparable. That is, a strict total order is a binary relation ${\displaystyle <}$ on some set ${\displaystyle X}$, which satisfies the following for all ${\displaystyle a,b}$ and ${\displaystyle c}$ in ${\displaystyle X}$:

Asymmetry follows from transitivity and irreflexivity; moreover, irreflexivity follows from asymmetry.