Total order

In mathematics, a total order, linear order or simple 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:

Related Topics:
Mathematics - Set - Binary relation - Antisymmetric - Transitive - Total

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: 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 paired with an associated total order on it is called a totally ordered set, a linearly ordered set, a simply 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.

Related Topics:
Reflexivity - Partial order

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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

~ ~ ~ ~ ~ ~ ~ ~ ~ ~