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]

A weak order on the set where is ranked below and and are of equal rank, and is ranked above and
I) representation as a strict weak order where is shown as an arrow from to ;
II) representations as a total preorder shown using arrows;
III) representation as an ordered partition, with the sets of the partition as dotted ellipses and the total order on these sets shown with arrows.
The 13 possible strict weak orderings on a set of three elements The only total orders are shown in black. Two orderings are connected by an edge if they differ by a single dichotomy.

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]


Share this article:

This article uses material from the Wikipedia article Weak ordering, and is written by contributors. Text is available under a CC BY-SA 4.0 International License; additional terms may apply. Images, videos and audio are available under their respective licenses.