Weak ordering

A term's definition may require additional properties that are not listed in this table.

In many cases another representation called a preferential arrangement based on a utility function is also possible.

They are used in computer science as part of partition refinement algorithms, and in the C++ Standard Library.

[2] In horse racing, the use of photo finishes has eliminated some, but not all, ties or (as they are called in this context) dead heats, so the outcome of a horse race may be modeled by a weak ordering.

[4] In the weak ordering describing this outcome, The Bruce would be first, Bug River and Lear Charm would be ranked after The Bruce but before all the other horses that finished, and the three horses that did not finish would be placed last in the order but tied with each other.

The points of the Euclidean plane may be ordered by their distance from the origin, giving another example of a weak ordering with infinitely many elements, infinitely many subsets of tied elements (the sets of points that belong to a common circle centered at the origin), and infinitely many points within these subsets.

In the results of a poll, one candidate may be clearly ahead of another, or the two candidates may be statistically tied, meaning not that their poll results are equal but rather that they are within the margin of error of each other.

Because of this possibility, rankings of this type are better modeled as semiorders than as weak orderings.

is irreflexive then the property known as "transitivity of incomparability" (defined below) is exactly the condition necessary and sufficient to guarantee that the relation "are

of these equivalence classes can be strictly totally ordered by a binary relation, also denoted by

Not every partial order obeys the transitive law for incomparability.

In the other direction, to define a strict weak ordering < from a total preorder

Two elements are equivalent in a total preorder if and only if they are incomparable in the corresponding strict weak ordering.

For sets of sufficiently small cardinality, a fourth axiomatization is possible, based on real-valued functions.

is a strictly increasing real-valued function defined on at least the range of

[12] However, there exist strict weak orders that have no corresponding real function.

is not assumed to be a surjective function, so a class of equivalent elements on

Semiorders generalize strict weak orderings, but do not assume transitivity of incomparability.

However, a different kind of move is possible, in which the weak orderings on a set are more highly connected.

Alternatively, a dichotomy may be defined as a Dedekind cut for a weak ordering.

Then a weak ordering may be characterized by its set of compatible dichotomies.

For a finite set of labeled items, every pair of weak orderings may be connected to each other by a sequence of moves that add or remove one dichotomy at a time to or from this set of dichotomies.

Moreover, the undirected graph that has the weak orderings as its vertices, and these moves as its edges, forms a partial cube.

In this geometric representation, the weak orderings on the set correspond to the faces of all different dimensions of the permutohedron (including the permutohedron itself, but not the empty set, as a face).

The codimension of a face gives the number of equivalence classes in the corresponding weak ordering.

[16] In this geometric representation the partial cube of moves on weak orderings is the graph describing the covering relation of the face lattice of the permutohedron.

The face lattice of the hexagon (again, including the hexagon itself as a face, but not including the empty set) has thirteen elements: one hexagon, six edges, and six vertices, corresponding to the one completely tied weak ordering, six weak orderings with one tie, and six total orderings.

As mentioned above, weak orders have applications in utility theory.

In these algorithms, a weak ordering on the vertices of a graph (represented as a family of sets that partition the vertices, together with a doubly linked list providing a total order on the sets) is gradually refined over the course of the algorithm, eventually producing a total ordering that is the output of the algorithm.

[18] In the Standard Library for the C++ programming language, the set and multiset data types sort their input by a comparison function that is specified at the time of template instantiation, and that is assumed to implement a strict weak ordering.

A weak order on the set where and are of equal rank, is ranked below them, and is ranked above them.
I) representation as a strict weak order where is shown as an arrow from to ;
II) representation 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.
The permutohedron on four elements, a three-dimensional convex polyhedron . It has 24 vertices, 36 edges, and 14 two-dimensional faces, which all together with the whole three-dimensional polyhedron correspond to the 75 weak orderings on four elements.