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. 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. 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. 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. In an example from the Maryland Hunt Cup steeplechase in 2007, The Bruce was the clear winner, but two horses Bug River and Lear Charm tied for second place, with the remaining horses farther back; three horses did not finish. 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. Although this ordering has a smallest element (the origin itself), it does not have any second-smallest elements, nor any largest element. Opinion polling in political elections provides an example of a type of ordering that resembles weak orderings, but is better modeled mathematically in other ways. 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. However, if candidate x is statistically tied with y, and y is statistically tied with z, it might still be possible for x to be clearly better than z, so being tied is not in this case a transitive relation. Because of this possibility, rankings of this type are better modeled as semiorders than as weak orderings. A strict weak ordering is a binary relation < on a set S that is a strict partial order (a transitive relation that is irreflexive, or equivalently, that is asymmetric) in which the relation 'neither a < b nor b < a' is transitive. Therefore, a strict weak ordering has the following properties: