nLab total order

Total orders

Total orders

Idea

A total order on a set is a way of ordering its elements to say that some elements precede others, with the understanding that any two elements can be compared one way or the other.

Definitions

Given a set SS, a total order on SS is a (binary) relation \leq with the following properties:

  • reflexivity: for any element xx of SS, xxx \leq x;
  • transitivity: whenever xyzx \leq y \leq z, then xzx \leq z;
  • antisymmetry: whenever xyxx \leq y \leq x, then x=yx = y;
  • totality: for any xx and yy in SS, xyx \leq y or yxy \leq x.

A toset is a set equipped with a total order.

Relation to simplices

The category of finite nonempty totally ordered sets and order-preserving maps is called Δ\Delta, the simplex category.

The category of all finite totally ordered sets and order-preserving maps is called Δ a\Delta_a, the augmented simplex category.

Relation to pseudolattices

Due to the totality of the order relation \leq, every pair of elements aa and bb has a join and meet, such that ab=aa \wedge b = a and ab=ba \vee b = b, or ab=ba \wedge b = b and ab=aa \vee b = a. This means that meets distribute over joins and joins distribute over meets, and additionally that both operations are associative, commutative, and idempotent, and so every total order is a pseudolattice, and every bounded total order is a lattice.

Relation to linear orders

A linear order is much like a total order, except that it is based on an irreflexive relation <\lt.

Using excluded middle, one can move between linear orders and total orders using negation; that is, the negation of a total order is a linear order and vice versa. Actually one usually swaps the order too, as follows:

  • xyx \leq y iff yxy \nless x;
  • x<yx \lt y iff yxy \nleq x.

One often sees x<yx \lt y defined as xyx \le y but xyx \ne y; this is equivalent, but doesn't show the duality explicitly. Similarly, one often sees xyx \leq y defined as x<yx \lt y or x=yx = y; this is not even equivalent constructively, although it is classically.

In classical mathematics, the distinction between total orders and linear orders is merely a terminological technicality, which is not always observed; more precisely, there is a natural bijection between the set of total orders on a given set SS and the set of linear orders on SS, and one distinguishes them by their notation. In constructive mathematics, however, they are irreducibly different.

For more, including why linear orders are more often useful in constructive mathematics, see linear order.

Last revised on June 18, 2021 at 19:24:36. See the history of this page for a list of all contributions to it.