preorders

Preorders are binary relations used to compare elements in a set in a way that is flexible enough to allow distinct elements to be mutually related. Formally, a preorder on a set S is a relation ≤ ⊆ S × S that is reflexive (for every x in S, x ≤ x) and transitive (if x ≤ y and y ≤ z, then x ≤ z). If, in addition, the relation is antisymmetric (x ≤ y and y ≤ x implies x = y), it becomes a partial order. If antisymmetry fails, the relation may relate distinct elements in both directions.

Every preorder induces an equivalence relation ~ defined by x ~ y if and only if x ≤ y and y ≤ x. The quotient set S/~, the set of equivalence classes, can be equipped with a partial order [x] ≤ [y] defined by x ≤ y. This establishes a standard connection between preorders and partial orders: every preorder yields a poset on the corresponding blocks of equivalent elements.

Examples help illustrate the distinction. The usual ≤ on the real numbers is both a preorder and a partial order. A simple non-antisymmetric preorder can be defined on a set partitioned into blocks by saying x ≤ y if x and y lie in the same block; within a block, elements are mutually related but distinct elements do not collapse to equality under ≤. In computer science and logic, preorders appear as reachability relations in directed graphs (a state can reach another, reflexively and transitively) or as subsumption relations in type systems.

In summary, preorders generalize the idea of comparison by relaxing antisymmetry, with the induced equivalence relation capturing when distinct elements are considered indistinguishable under the preorder.