# Weak ordering

In mathematics, especially order theory, a **weak ordering** is a mathematical formalization of the intuitive notion of a ranking of a set, some of whose members may be tied with each other. Weak orders are a generalization of totally ordered sets (rankings without ties) and are in turn generalized by partially ordered sets and preorders.[1]

Transitive binary relations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

indicates that the column's property is required by the definition of the row's term (at the very left). For example, the definition of an equivalence relation requires it to be symmetric. ✗ indicates that the property may, or may not hold. All definitions tacitly require the homogeneous relation be transitive: for all if and then and there are additional properties that a homogeneous relation may satisfy. |

There are several common ways of formalizing weak orderings, that are different from each other but cryptomorphic (interconvertable with no loss of information): they may be axiomatized as **strict weak orderings** (partially ordered sets in which incomparability is a transitive relation), as **total preorders** (transitive binary relations in which at least one of the two possible relations exists between every pair of elements), or as **ordered partitions** (partitions of the elements into disjoint subsets, together with a total order on the subsets). In many cases another representation called a **preferential arrangement** based on a utility function is also possible.

Weak orderings are counted by the ordered Bell numbers. They are used in computer science as part of partition refinement algorithms, and in the C++ Standard Library.[2]