total order (original) (raw)

A totally ordered set (or linearly ordered set) is a poset (T,≤) which has the property of comparability:

• •
  for all x,y∈T, either x≤y or y≤x.

In other words, a totally ordered set is a set T with a binary relation ≤ on it such that the following hold for all x,y,z∈T:

• •
• •
  If x≤y and y≤x, then x=y. (antisymmetry)
• •
• •
  Either x≤y or y≤x. (comparability)

The binary relation ≤ is then called a total order or a linear order (or total ordering or linear ordering). A totally ordered set is also sometimes called a chain, especially when it is considered as a subset of some other poset. If every nonempty subset of T has a least element, then the total order is called a well-order (http://planetmath.org/WellOrderedSet).

Some people prefer to define the binary relation < as a total order, rather than ≤. In this case, < is required to be transitive (http://planetmath.org/Transitive3) and to obey the law of trichotomy. It is straightforward to check that this is equivalent to the above definition, with the usual relationship between < and ≤(that is, x≤y if and only if either x<y or x=y).

A totally ordered set can also be defined as a lattice (T,∨,∧) in which the following property holds:

• •
  for all x,y∈T, either x∧y=x or x∧y=y.

Then totally ordered sets are distributive lattices (http://planetmath.org/DistributiveLattice).