Preorder

In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. The name preorder is meant to suggest that preorders are almost partial orders, but not quite, as they are not necessarily antisymmetric.

A natural example of a preorder is the divides relation "x divides y" between integers. This relation is reflexive as every integer divides itself. It is also transitive. But it is not antisymmetric, because e.g. ${\displaystyle 1}$ divides ${\displaystyle -1}$ and ${\displaystyle -1}$ divides ${\displaystyle 1}$. It is to this preorder that "least" refers in the phrase "least common multiple" (in contrast, using the natural order on integers, e.g. ${\displaystyle 4}$ and ${\displaystyle 6}$ have the common multiples ${\displaystyle 24}$, ${\displaystyle 12}$, ${\displaystyle 0}$, ${\displaystyle -12}$, ${\displaystyle -24}$, ..., but no least one).

Preorders are closely related to equivalence relations and (non-strict) partial orders. Both of these are special cases of a preorder: an antisymmetric preorder is a partial order, and a symmetric preorder is an equivalence relation. Moreover, a preorder on a set ${\displaystyle X}$ can equivalently be defined as an equivalence relation on ${\displaystyle X}$, together with a partial order on the set of equivalence class, cf. picture. Like partial orders and equivalence relations, preorders (on a nonempty set) are never asymmetric.

A preorder can be visualized as a directed graph, with elements of the set corresponding to vertices, and the order relation between pairs of elements corresponding to the directed edges between vertices. The converse is not true: most directed graphs are neither reflexive nor transitive. A preorder that is antisymmetric no longer has cycles; it is a partial order, and corresponds to a directed acyclic graph. A preorder that is symmetric is an equivalence relation; it can be thought of as having lost the direction markers on the edges of the graph. In general, a preorder's corresponding directed graph may have many disconnected components.

A preorder is often denoted ${\displaystyle \,\lesssim \,}$ or ${\displaystyle \,\leq \,}$.

A binary relation ${\displaystyle \,\lesssim \,}$ on a set ${\displaystyle X}$ is called a preorder or quasiorder if it is reflexive and transitive; that is, if it satisfies:

A set that is equipped with a preorder is called a preordered set (or proset).

Given a preorder ${\displaystyle \,\lesssim \,}$ on ${\displaystyle X}$ one may define an equivalence relation ${\displaystyle \,\sim \,}$ on ${\displaystyle X}$ by $${\displaystyle a\sim b\quad {\text{ if }}\quad a\lesssim b\;{\text{ and }}\;b\lesssim a.}$$ The resulting relation ${\displaystyle \,\sim \,}$ is reflexive since the preorder ${\displaystyle \,\lesssim \,}$ is reflexive; transitive by applying the transitivity of ${\displaystyle \,\lesssim \,}$ twice; and symmetric by definition.