Total order

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

A total order or linear order on a set X is a binary relation that is reflexive, antisymmetric, transitive and total. This means that, if we denote the relation by <=, it holds for all a, b and c in X:

  • (reflexivity) a <= a
  • (antisymmetry) if a <= b and b <= a then a = b
  • (transitivity) if a <= b and b <= c then a <= c
  • (totalness) a <= b or b <= a

A set with a total order on it is called a totally ordered set.

Because a binary relation that is reflexive, antisymmetric and transitive is called a partial order, 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 {a v b, a ^ b} = {a, b} for all a, b. We then write a <= b if and only if a = a ^ b.

If a and b are members of a totally ordered set, we may write a < b if a <= b and ab. 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. The totally ordered set X turns into a topological space if we define a subset to be open if and only if it is a (possibly infinite) union of such open intervals. This is called the order topology on X; it is always a normal Hausdorff space. Unless otherwise stated, it is understood that this topology is being used on a totally ordered set.

The set of natural numbers is the unique (up to isomorphism) 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, that is, have non-empty (a, b) for every a < b, is the rational numbers. The unique smallest unbounded connected totally ordered set is the real numbers.

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