Strict Weak Ordering

Suppose that \(<\) is a binary relation on a set \(S\) (that is, \(<\) is a subset of \(S \times S\)) and as usual, write \(x < y\) and say that \(x < y\) holds or is true if and only if \((x, y) \in <\).

Preliminaries on incomparability and transitivity of incomparability

Two elements \(x\) and \(y\) of \(S\) are said to be incomparable with respect to \(<\) if neither \(x < y\) nor \(y < x\) is true. Incomparability with respect to \(<\) is itself a symmetric relation on \(S\) that is reflexive if and only if \(<\) is irreflexive (meaning that \(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 relation \(\le\) on \(S\) by declaring that \[ x \le 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: \(x \le y\) if and only if \(x < y\) or \(x = y\).

Definition

A strict weak ordering on a set \(S\) is a strict partial order \(<\) on \(S\) for which the incomparability relation induced on \(S\) by \(<\) is a transitive relation. Explicitly, a strict weak order on \(S\) is a relation \(<\) on \(S\) that has all four of the following properties:

  1. Irreflexivity: For all \(x\in S\), it is not true that \(x < x\).

  2. Transitivity: For all \(x, y, z \in S\), if \(x < y\) and \(y < z\) then \(x < z\).

  3. Asymmetry: For all \(x, y \in S\), if \(x < y\) is true then \(y < x\) is false.

  4. Transitivity of incomparability: For all \(x, y, z \in S\), if \(x\) is incomparable with \(y\) and if \(y\) is incomparable with \(z\), then \(x\) is incomparable with \(z\).

Properties (1), (2), and (3) are the defining properties of a strict partial order, although this list of these three properties is somewhat redundant in that asymmetry implies irreflexivity, and in that irreflexivity and transitivity together imply asymmetry. A strict partial order \(<\) is a strict weak order if and only if its induced incomparability relation is an equivalence relation.