Strict weak ordering

The 13 possible strict weak orderings on a set of three elements {a, b, c}. The only partially ordered sets are coloured, while totally ordered ones are in black. Two orderings are shown as connected by an edge if they differ by a single dichotomy.

In mathematics, especially order theory, 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.

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.

As a non-example, consider the partial order in the set {a, b, c} defined by the relationship b < c. The pairs a,b and a,c are incomparable but b and c are related, so incomparability does not form an equivalence relation and this example is not a strict weak ordering.

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 (asymmetric).
• 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 asymmetry 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).

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

Total preorders

Strict weak orders are very closely related to total preorders or (non-strict) weak orders, and the same mathematical concepts that can be modeled with strict weak orderings can be modeled equally well with total preorders. A total preorder or weak order is a preorder that is total; that is, no pair of items is incomparable. A total preorder $\lesssim$ satisfies the following properties:

• For all x, y, and z, if x $\lesssim$ y and y $\lesssim$ z then x $\lesssim$ z (transitivity).
• For all x and y, x $\lesssim$ y or y $\lesssim$ x (totality).
  • Hence, for all x, x $\lesssim$ x (reflexivity).

A total order is a total preorder which is antisymmetric, in other words, which is also a partial order.

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. Thus we take the inverse of the complement: for a strict weak ordering <, define a total preorder $\lesssim$ by setting x $\lesssim$ y whenever it is not the case that y < x. In the other direction, to define a strict weak ordering < from a total preorder $\lesssim$, set x < y whenever it is not the case that y $\lesssim$ x.

For a strict weak order "<" another associated reflexive relation is its reflexive closure, a (non-strict) partial order "≤". The two associated reflexive relations differ with regard to different a and b for which neither a < b nor b < a: in the total preorder we get a $\lesssim$ b and b $\lesssim$ a, while in the (non-strict) partial order we get neither a ≤ b nor b ≤ a. For strict total orders these two associated reflexive relations are the same: the corresponding (non-strict) total order. The reflexive closure of a strict weak ordering is a type of series-parallel partial order.

In any preorder there is a corresponding equivalence relation where two elements x and y are defined as equivalent if x $\lesssim$ y and y $\lesssim$ x. In the case of a total preorder the corresponding partial order on the set of equivalence classes is a total order. Two elements are equivalent in a total preorder if and only if they are incomparable in the corresponding strict weak ordering.

Representing weak orderings by functions

If X is any set and f a real-valued function on X then f induces a strict weak order on X by setting

• a < b if and only if f(a) < f(b)

The associated total preorder is given by

• a $\lesssim$ b if and only if f(a) ≤ f(b)

and the associated equivalence by

• a $\sim \!$ b if and only if f(a) = f(b)

The relations do not change when f is replaced by g o f (composite function), where g is a strictly increasing real-valued function defined on at least the range of f.

Thus e.g. a utility function defines a preference relation.

If X is finite or countable, every weak order can be represented by a function in this way (see, e.g., Roberts 1979, Theorem 3.1). However, there exist strict weak orders that have no corresponding real function. For example, there is no such function for the lexicographic order on Rⁿ. Thus, while in most preference relation models the relation defines a utility function up to order-preserving transformations, there is no such function for lexicographic preferences.

More generally, if X is a set, and Y is a set with a strict weak ordering "<", and f a function from X to Y, then f induces a strict weak ordering on X by setting

• a < b if and only if f(a) < f(b)

The associated total preorder is given by

• a $\lesssim$ b if and only if f(a) $\lesssim$ f(b)

and the associated equivalence by

• a $\sim\!$ b if and only if f(a) $\sim\!$ f(b)

f is not necessarily an injective function, so for example a class of 2 equivalent elements on Y may induce a class of 5 equivalent elements on X. Also f is not necessarily an surjective function, so a class of 2 equivalent elements on Y may induce a class of only one element on X, or no class at all. There is a corresponding injective function g that maps the partition on X to that on Y. Thus, in the case of finite partitions, the number of classes in X is less than or equal to the number of classes on Y.

Examples

On the 2-dimensional real plane:

• f(x, y) = x + y
• f(x, y) = min(x, y)

In the case of preferences with regard to an amount of x of one product and y of the other, the first corresponds to the case that the products can replace each other, the other that they can only be used in combination.

The number of total preorders

The number of distinct total preorders on an n-element set is given by the following sequence (sequence A000670 in OEIS):

Number of n-element binary relations of different types
n	all	transitive	reflexive	preorder	partial order	total preorder	total order	equivalence relation
0	1	1	1	1	1	1	1	1
1	2	2	1	1	1	1	1	1
2	16	13	4	4	3	3	2	2
3	512	171	64	29	19	13	6	5
4	65536	3994	4096	355	219	75	24	15
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

These numbers are also called the Fubini numbers or ordered Bell numbers.

As explained above, there is a 1-to-1 correspondence between total preorders and pairs (partition, total order). Thus the number of total preorders is the sum of the number of total orders on every partition. For example:

• for n = 3:
  • 1 partition of 3, giving 1 total preorder (each element is related to each element)
  • 3 partitions of 2 + 1, giving 3 × 2 = 6 total preorders
  • 1 partition of 1 + 1 + 1, giving 6 total preorders (the total orders)

i.e. together 13 total preorders.

• for n = 4:
  • 1 partition of 4, giving 1 total preorder (each element is related to each element)
  • 7 partitions with two classes (4 of 3 + 1 and 3 of 2 + 2), giving 7 × 2 = 14 total preorders
  • 6 partitions of 2+1+1, giving 6 × 6 = 36 total preorders
  • 1 partition of 1+1+1+1, giving 24 total preorders (the total orders)

i.e. together 75 total preorders.

Compare the Bell numbers, here 5 and 15: the number of partitions, i.e., the number of equivalence relations.

Strict total order

A strict weak order that is trichotomous is called a strict total order. The total preorder which is the inverse of its complement is in this case a total order.

References

• Fishburn, Peter C. (1970), "Intransitive indifference in preference theory: a survey", Operations Research 18 (2): 207–228, doi:10.1287/opre.18.2.207 .
• Roberts, Fred S. (1979), Measurement Theory, with Applications to Decisionmaking, Utility, and the Social Sciences, Encyclopedia of Mathematics and its Applications, 7, Addison-Wesley, ISBN 9780201135060 .