Strict Weak Ordering - Total Preorders

Not to be confused with weak order of permutations.

Strict weak orders are very closely related to total preorders or (non-strict) weak orders, and the same mathematical concepts that can be modeled with strict weak orderings can be modeled equally well with total preorders. A total preorder or weak order is a preorder that is total; that is, no pair of items is incomparable. A total preorder satisfies the following properties:

• For all x, y, and z, if x y and y z then x z (transitivity).
• For all x and y, x y or y x (totality).
  • Hence, for all x, x x (reflexivity).

A total order is a total preorder which is antisymmetric, in other words, which is also a partial order.

The complement of a strict weak order is a total preorder, and vice versa, but it seems more natural to relate strict weak orders and total preorders in a way that preserves rather than reverses the order of the elements. Thus we take the inverse of the complement: for a strict weak ordering <, define a total preorder by setting x y whenever it is not the case that y < x. In the other direction, to define a strict weak ordering < from a total preorder, set x < y whenever it is not the case that y x.

For a strict weak order "<" another associated reflexive relation is its reflexive closure, a (non-strict) partial order "≤". The two associated reflexive relations differ with regard to different a and b for which neither a < b nor b < a: in the total preorder we get a b and b a, while in the (non-strict) partial order we get neither a ≤ b nor b ≤ a. For strict total orders these two associated reflexive relations are the same: the corresponding (non-strict) total order. The reflexive closure of a strict weak ordering is a type of series-parallel partial order.

In any preorder there is a corresponding equivalence relation where two elements x and y are defined as equivalent if x y and y x. In the case of a total preorder the corresponding partial order on the set of equivalence classes is a total order. Two elements are equivalent in a total preorder if and only if they are incomparable in the corresponding strict weak ordering.