Weak ordering

Preliminaries on incomparability and transitivity of incomparability

Two elements ${\displaystyle x}$ and ${\displaystyle y}$ of ${\displaystyle S}$ are said to be incomparable with respect to ${\displaystyle \,<\,}$ if neither ${\displaystyle x<y}$ nor ${\displaystyle y<x}$ is true.[1] Incomparability with respect to ${\displaystyle \,<\,}$ is itself a homogeneous symmetric relation on ${\displaystyle S}$ that is reflexive if and only if ${\displaystyle \,<\,}$ is irreflexive (meaning that ${\displaystyle x<x}$ is always false), which may be assumed so that transitivity is the only property this "incomparability relation" needs in order to be an equivalence relation. Define also an induced homogeneous relation ${\displaystyle \,\lesssim \,}$ on ${\displaystyle S}$ by declaring that

$${\displaystyle x\lesssim y{\text{ is true }}\quad {\text{ if and only if }}\quad y<x{\text{ is false}}}$$

where importantly, this definition is not necessarily the same as: ${\displaystyle x\lesssim y}$ if and only if ${\displaystyle x<y{\text{ or }}x=y.}$ Two elements ${\displaystyle x,y\in S}$ are incomparable with respect to ${\displaystyle \,<\,}$ if and only if ${\displaystyle x{\text{ and }}y}$ are equivalent with respect to ${\displaystyle \,\lesssim \,}$ (or less verbosely, ${\displaystyle \,\lesssim }$-equivalent), which by definition means that both ${\displaystyle x\lesssim y{\text{ and }}y\lesssim x}$ are true. The relation "are incomparable with respect to ${\displaystyle \,<}$" is thus identical to (that is, equal to) the relation "are ${\displaystyle \,\lesssim }$-equivalent" (so in particular, the former is transitive if and only if the latter is). When ${\displaystyle \,<\,}$ 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 ${\displaystyle \,\lesssim }$-equivalent" does indeed form an equivalence relation on ${\displaystyle S.}$ When this is the case, it allows any two elements ${\displaystyle x,y\in S}$ satisfying ${\displaystyle x\lesssim y{\text{ and }}y\lesssim x}$ to be identified as a single object (specifically, they are identified together in their common equivalence class).

Definition

A strict weak ordering on a set ${\displaystyle S}$ is a strict partial order ${\displaystyle \,<\,}$ on ${\displaystyle S}$ for which the incomparability relation induced on ${\displaystyle S}$ by ${\displaystyle \,<\,}$ is a transitive relation.[1] Explicitly, a strict weak order on ${\displaystyle S}$ is a homogeneous relation ${\displaystyle \,<\,}$ on ${\displaystyle S}$ that has all four of the following properties:

1. Irreflexivity: For all ${\displaystyle x\in S,}$ it is not true that ${\displaystyle x<x.}$
   • This condition holds if and only if the induced relation ${\displaystyle \,\lesssim \,}$ on ${\displaystyle S}$ is reflexive, where ${\displaystyle \,\lesssim \,}$ is defined by declaring that ${\displaystyle x\lesssim y}$ is true if and only if ${\displaystyle y<x}$ is false.
2. Transitivity: For all ${\displaystyle x,y,z\in S,}$ if ${\displaystyle x<y{\text{ and }}y<z}$ then ${\displaystyle x<z.}$
3. Asymmetry: For all ${\displaystyle x,y\in S,}$ if ${\displaystyle x<y}$ is true then ${\displaystyle y<x}$ is false.
4. Transitivity of incomparability: For all ${\displaystyle x,y,z\in S,}$ if ${\displaystyle x}$ is incomparable with ${\displaystyle y}$ (meaning that neither ${\displaystyle x<y}$ nor ${\displaystyle y<x}$ is true) and if ${\displaystyle y}$ is incomparable with ${\displaystyle z,}$ then ${\displaystyle x}$ is incomparable with ${\displaystyle z.}$
   • Two elements ${\displaystyle x{\text{ and }}y}$ are incomparable with respect to ${\displaystyle \,<\,}$ if and only if they are equivalent with respect to the induced relation ${\displaystyle \,\lesssim \,}$ (which by definition means that ${\displaystyle x\lesssim y{\text{ and }}y\lesssim x}$ are both true), where as before, ${\displaystyle x\lesssim y}$ is declared to be true if and only if ${\displaystyle y<x}$ is false. Thus this condition holds if and only if the symmetric relation on ${\displaystyle S}$ defined by "${\displaystyle x{\text{ and }}y}$ are equivalent with respect to ${\displaystyle \,\lesssim \,}$" is a transitive relation, meaning that whenever ${\displaystyle x{\text{ and }}y}$ are ${\displaystyle \,\lesssim }$-equivalent and also ${\displaystyle y{\text{ and }}z}$ are ${\displaystyle \,\lesssim }$-equivalent then necessarily ${\displaystyle x{\text{ and }}z}$ are ${\displaystyle \,\lesssim }$-equivalent. This can also be restated as: whenever ${\displaystyle x\lesssim y{\text{ and }}y\lesssim x}$ and also ${\displaystyle y\lesssim z{\text{ and }}z\lesssim y}$ then necessarily ${\displaystyle x\lesssim z{\text{ and }}z\lesssim x.}$

Properties (1), (2), and (3) are the defining properties of a strict partial order, although there is some redundancy in this list as asymmetry (3) implies irreflexivity (1), and also because irreflexivity (1) and transitivity (2) together imply asymmetry (3).[6] The incomparability relation is always symmetric and it will be reflexive if and only if ${\displaystyle \,<\,}$ is an irreflexive relation (which is assumed by the above definition). Consequently, a strict partial order ${\displaystyle \,<\,}$ is a strict weak order if and only if its induced incomparability relation is an equivalence relation. In this case, its equivalence classes partition ${\displaystyle S}$ and moreover, the set ${\displaystyle {\mathcal {P}}}$ of these equivalence classes can be strictly totally ordered by a binary relation, also denoted by ${\displaystyle \,<,}$ that is defined for all ${\displaystyle A,B\in {\mathcal {P}}}$ by:

${\displaystyle A<B{\text{ if and only if }}a<b}$ for some (or equivalently, for all) representatives ${\displaystyle a\in A{\text{ and }}b\in B.}$

Conversely, any strict total order on a partition ${\displaystyle {\mathcal {P}}}$ of ${\displaystyle S}$ gives rise to a strict weak ordering ${\displaystyle \,<\,}$ on ${\displaystyle S}$ defined by ${\displaystyle a<b}$ if and only if there exists sets ${\displaystyle A,B\in {\mathcal {P}}}$ in this partition such that ${\displaystyle a\in A,b\in B,{\text{ and }}A<B.}$

Not every partial order obeys the transitive law for incomparability. For instance, consider the partial order in the set ${\displaystyle \{a,b,c\}}$ defined by the relationship ${\displaystyle b<c.}$ The pairs ${\displaystyle a,b{\text{ and }}a,c}$ are incomparable but ${\displaystyle b}$ and ${\displaystyle c}$ are related, so incomparability does not form an equivalence relation and this example is not a strict weak ordering.

For transitivity of incomparability, each of the following conditions is necessary, and for strict partial orders also sufficient:

• If ${\displaystyle x<y}$ then for all ${\displaystyle z,}$ either ${\displaystyle x<z{\text{ or }}z<y}$ or both.
• If ${\displaystyle x}$ is incomparable with ${\displaystyle y}$ then for all ${\displaystyle z}$, either (${\displaystyle x<z{\text{ and }}y<z}$) or (${\displaystyle z<x{\text{ and }}z<y}$) or (${\displaystyle z}$ is incomparable with ${\displaystyle x}$ and ${\displaystyle z}$ is incomparable with ${\displaystyle y}$).

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 in which any two elements are comparable.[7] A total preorder ${\displaystyle \,\lesssim \,}$ satisfies the following properties:

• Transitivity: For all ${\displaystyle x,y,{\text{ and }}z,}$ if ${\displaystyle x\lesssim y{\text{ and }}y\lesssim z}$ then ${\displaystyle x\lesssim z.}$
• Strong connectedness: For all ${\displaystyle x{\text{ and }}y,}$ ${\displaystyle x\lesssim y{\text{ or }}y\lesssim x.}$
  • Which implies reflexivity: for all ${\displaystyle x,}$ ${\displaystyle x\lesssim x.}$

A total order is a total preorder which is antisymmetric, in other words, which is also a partial order. Total preorders are sometimes also called preference relations.

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 converse of the complement: for a strict weak ordering ${\displaystyle \,<,}$ define a total preorder ${\displaystyle \,\lesssim \,}$ by setting ${\displaystyle x\lesssim y}$ whenever it is not the case that ${\displaystyle y<x.}$ In the other direction, to define a strict weak ordering < from a total preorder ${\displaystyle \,\lesssim ,}$ set ${\displaystyle x<y}$ whenever it is not the case that ${\displaystyle y\lesssim x.}$[8]

In any preorder there is a corresponding equivalence relation where two elements ${\displaystyle x}$ and ${\displaystyle y}$ are defined as equivalent if ${\displaystyle x\lesssim y{\text{ 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.

A partition of a set ${\displaystyle S}$ is a family of non-empty disjoint subsets of ${\displaystyle S}$ that have ${\displaystyle S}$ as their union. A partition, together with a total order on the sets of the partition, gives a structure called by Richard P. Stanley an ordered partition[9] and by Theodore Motzkin a list of sets.[10] An ordered partition of a finite set may be written as a finite sequence of the sets in the partition: for instance, the three ordered partitions of the set ${\displaystyle \{a,b\}}$ are

$${\displaystyle \{a\},\{b\},}$$

$${\displaystyle \{b\},\{a\},\;{\text{ and }}}$$

$${\displaystyle \{a,b\}.}$$

In a strict weak ordering, the equivalence classes of incomparability give a set partition, in which the sets inherit a total ordering from their elements, giving rise to an ordered partition. In the other direction, any ordered partition gives rise to a strict weak ordering in which two elements are incomparable when they belong to the same set in the partition, and otherwise inherit the order of the sets that contain them.

For sets of sufficiently small cardinality, a third axiomatization is possible, based on real-valued functions. If ${\displaystyle X}$ is any set then a real-valued function ${\displaystyle f:X\to \mathbb {R} }$ on ${\displaystyle X}$ induces a strict weak order on ${\displaystyle X}$ by setting

$${\displaystyle a<b{\text{ if and only if }}f(a)<f(b).}$$

The associated total preorder is given by setting ${\displaystyle a{}\lesssim {}b{\text{ if and only if }}f(a)\leq f(b)}$ and the associated equivalence by setting ${\displaystyle a{}\sim {}b{\text{ if and only if }}f(a)=f(b).}$

The relations do not change when ${\displaystyle f}$ is replaced by ${\displaystyle g\circ f}$ (composite function), where ${\displaystyle g}$ is a strictly increasing real-valued function defined on at least the range of ${\displaystyle f.}$ Thus for example, a utility function defines a preference relation. In this context, weak orderings are also known as preferential arrangements.[11]

If ${\displaystyle X}$ is finite or countable, every weak order on ${\displaystyle X}$ can be represented by a function in this way.[12] However, there exist strict weak orders that have no corresponding real function. For example, there is no such function for the lexicographic order on ${\displaystyle \mathbb {R} ^{n}.}$ 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 ${\displaystyle X}$ is a set, ${\displaystyle Y}$ is a set with a strict weak ordering ${\displaystyle \,<,\,}$ and ${\displaystyle f:X\to Y}$ is a function, then ${\displaystyle f}$ induces a strict weak ordering on ${\displaystyle X}$ by setting

$${\displaystyle a<b{\text{ if and only if }}f(a)<f(b).}$$

As before, the associated total preorder is given by setting ${\displaystyle a{}\lesssim {}b{\text{ if and only if }}f(a){}\lesssim {}f(b),}$ and the associated equivalence by setting ${\displaystyle a{}\sim {}b{\text{ if and only if }}f(a){}\sim {}f(b).}$ It is not assumed here that ${\displaystyle f}$ is an injective function, so a class of two equivalent elements on ${\displaystyle Y}$ may induce a larger class of equivalent elements on ${\displaystyle X.}$ Also, ${\displaystyle f}$ is not assumed to be a surjective function, so a class of equivalent elements on ${\displaystyle Y}$ may induce a smaller or empty class on ${\displaystyle X.}$ However, the function ${\displaystyle f}$ induces an injective function that maps the partition on ${\displaystyle X}$ to that on ${\displaystyle Y.}$ Thus, in the case of finite partitions, the number of classes in ${\displaystyle X}$ is less than or equal to the number of classes on ${\displaystyle Y.}$

The number of distinct weak orders (represented either as strict weak orders or as total preorders) on an ${\displaystyle n}$-element set is given by the following sequence (sequence A000670 in the OEIS):

Note that S(n, k) refers to Stirling numbers of the second kind.

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

For example, for a set of three labeled items, there is one weak order in which all three items are tied. There are three ways of partitioning the items into one singleton set and one group of two tied items, and each of these partitions gives two weak orders (one in which the singleton is smaller than the group of two, and one in which this ordering is reversed), giving six weak orders of this type. And there is a single way of partitioning the set into three singletons, which can be totally ordered in six different ways. Thus, altogether, there are 13 different weak orders on three items.

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.

Unlike for partial orders, the family of weak orderings on a given finite set is not in general connected by moves that add or remove a single order relation to or from a given ordering. For instance, for three elements, the ordering in which all three elements are tied differs by at least two pairs from any other weak ordering on the same set, in either the strict weak ordering or total preorder axiomatizations. However, a different kind of move is possible, in which the weak orderings on a set are more highly connected. Define a dichotomy to be a weak ordering with two equivalence classes, and define a dichotomy to be compatible with a given weak ordering if every two elements that are related in the ordering are either related in the same way or tied in the dichotomy. 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.[15]

Geometrically, the total orderings of a given finite set may be represented as the vertices of a permutohedron, and the dichotomies on this same set as the facets of the permutohedron. 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.

For instance, for ${\displaystyle n=3,}$ the permutohedron on three elements is just a regular hexagon. 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. The graph of moves on these 13 weak orderings is shown in the figure.