Strict weak ordering
From Wikipedia, the free encyclopedia
In mathematics, especially order theory, a strict weak ordering is a binary relation < on a set S that is a strict partial order in which incomparability forms an equivalence relation. The equivalence classes of this incomparability relation partition the elements of S, and are totally ordered by <. Conversely, any total order on a partition of S gives rise to a strict weak ordering in which x < y if and only if there exists sets A and B in the partition with x in A, y in B, and A < B in the total order. Strict weak orders are often used in mathematical psychology to model preferences with indifference. The concept of a strict weak ordering also plays a crucial role in the C++ Standard Template Library, as many of its methods for ordering objects expect to be given a predicate defining a strict weak ordering, defaulting to the standard less-than operator if no predicate is given.
As an example, suppose that we have a strict partial order in which a < b < d and a < c < d, with no other elements or relationships. Then this is a strict weak order in which b and c are incomparable. However, consider instead the partial order defined by the relationships a < b < c < e and a < d < e. The pairs b,d and d,c are incomparable but b and c are related, so incomparability does not form an equivalence relation and this second example is not a strict weak ordering.
Contents |
[edit] Properties
A strict weak ordering has the following properties. For all x and y in S,
- For all x, it is not the case that x < x (irreflexivity).
- For all x ≠ y, if x < y then it is not the case that y < x (antisymmetry).
- For all x, y, and z, if x < y and y < z then x < z (transitivity).
- For all x, y, and z, if x is incomparable with y, and y is incomparable with z, then x is incomparable with z (transitivity of equivalence).
Note that this list of properties is somewhat redundant, as antisymmetry follows readily from irreflexivity and transitivity. Transitivity of equivalence can also be stated in the following simpler form:
- If x < y, then for all z either x < z or z < y (or both).
[edit] Total preorders
Strict weak orderings are very closely related to total preorders, and the same mathematical concepts that can be modeled with strict weak orderings can be modeled equally well with total preorders. A total preorder is a preorder that is total; that is, no pair of items is incomparable. A total preorder ≤ satisfies the following properties:
- For all x, x ≤ x (reflexivity).
- 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).
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. To do so, 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.
In a total preorder, we may define two elements x and y as equivalent if x ≤ y and y ≤ x. It follows from the properties of a total preorder that this is an equivalence relation. Two elements are equivalent in a total preorder if and only if they are incomparable in the corresponding strict weak ordering.
The difference between a total preorder and a total order is that a total preorder (since it is only a preorder) is not required to be antisymmetric.
[edit] The number of weak orders
The number of distinct weak orderings on an n-element set is given by the following sequence:
- 1, 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563, 1622632573 (sequence A000670 in OEIS).
These numbers are also called the Fubini numbers or ordered Bell numbers.
[edit] References
- Fishburn, Peter C. (1970). "Intransitive indifference in preference theory: a survey". Operations Research 18: 207–228.
