Preorder

Definition

A preorder (or pre-order) on a set $A$ is a relation $\le :A\to A\to \mathrm{Prop}$ that is:

• reflexive: $\forall x:A.x\le x$
• transitive: $\forall x,y,z:A.x\le y\to y\le z\to x\le z$

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

Quotient to a Partial Order

A preorder need not be anti-symmetric: distinct elements $x\ne y$ may satisfy both $x\le y$ and $y\le x$. Such elements are called equivalent under the preorder. The relation $x\sim y⟺x\le y\wedge y\le x$ is an equivalence relation, and the quotient $A/\sim$ inherits a partial order from $\le$.

Categorical Perspective

Every preorder $(A,\le )$ gives rise to a thin category whose objects are elements of $A$ and where there is exactly one morphism $x\to y$ iff $x\le y$. Functors between thin categories correspond to order-preserving maps (monotone maps). Under this correspondence:

• partial orders are skeletal thin categories
• equivalences of categories correspond to equivalence of preorders (up to the quotient partial order)

Examples

• Any partial order is a preorder.
• The divisibility relation $m\mid n$ on $\mathbb{N}$ is a partial order, hence a preorder.
• The reachability relation on the nodes of a directed graph is a preorder (reflexivity by empty path, transitivity by concatenation).
• HoTT uses univalent preorders to model proof-relevant order structure.

Related Concepts

• Partial Order
• Total Ordering
• Equivalence Relation
• Reflexive Relation
• Transitive Relation
• Thin Category
• Predicate

References

• munkres2000-topology