In mathematics, a total order or linear order on a set X is any binary relation on X that is antisymmetric, transitive, and total. This means that, if we denote the relation by ≤, the following statements hold for all a, b and c in X:

if a ≤ b and b ≤ a then a = b (antisymmetry)

if a ≤ b and b ≤ c then a ≤ c (transitivity)

a ≤ b or b ≤ a (totalness)

A set with a total order on it is called a totally ordered set, a linearly ordered set, or a chain. The totalness property can be stated thus: that any pair of elements in the chain are mutually comparable.

Notice that the totalness condition 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. It follows that a total order can also be defined as a partial order that is total.

Alternatively, one may define a totally ordered set as a particular kind of lattice, namely one in which we have for all a, b. We then write a ≤ b if and only if .

If a and b are members of a totally ordered set, we may write a < b if a ≤ b and a ≠ b. The binary relation < is then transitive (a < b and b < c implies a < c) and trichotomous (one and only one of a < b, b < a and a = b is true). In fact, we can define a total order to be a transitive trichotomous binary relation <, and then define a ≤ b to mean a < b or a = b, and this definition can be shown to be equivalent to the one given at the beginning of this article.

For any totally ordered set X we can define the open intervals (a, b) = {x : a < x and x < b}, (−∞, b) = {x : x < b}, (a, ∞) = {x : a < x} and (−∞, ∞) = X. We can use open intervals to define a topology on any ordered set, the order topology.

Examples

The following is valid up to order isomorphism:

The set of natural numbers is the unique smallest totally ordered set with no upper bound. Similarly, the unique smallest totally ordered set with neither an upper nor a lower bound is the integers. The unique smallest unbounded totally ordered set which also happens to be dense in the sense that (a, b) is non-empty for every a < b, is the rational numbers. The unique smallest unbounded connected totally ordered set is the real numbers.

Note that subsets are possible, which in a way are smaller, but that they are order isomorphic and therefore not counting as smaller. For example, instead of natural numbers and integers we can take the even ones, and instead of all rational numbers we can take those with a finite decimal expansion.

Any set of cardinal numbers or ordinal numbers is totally ordered (in fact, even well-ordered).

See also: happened-before