quasiordered

A quasiordered set, or preorder, is a set equipped with a binary relation that is reflexive and transitive. Concretely, a relation ≤ on a set X is a quasiorder if for all x in X, x ≤ x (reflexivity), and for all x, y, z in X, x ≤ y and y ≤ z imply x ≤ z (transitivity).

Quasiorders need not be antisymmetric. If a ≤ b and b ≤ a imply a = b, the relation is a partial order. If, in addition, every pair of elements is comparable (a ≤ b or b ≤ a for all a, b in X), the quasiorder is a total or linear order. Thus every partial order is a quasiorder, but not every quasiorder is a partial order.

A quasiordered set can be viewed as a thin category, where the objects are the elements and there is at most one morphism from x to y, namely x ≤ y. Its structure can be simplified by passing to the quotient by the induced equivalence relation x ~ y iff x ≤ y and y ≤ x. This ~ partitions X into equivalence classes, and the set of classes X/~ inherits a partial order defined by [x] ≤ [y] if x ≤ y.

Common examples include:

- The natural numbers with the usual ≤ relation; it is a quasiorder and, in fact, a partial/total order.

- The divisibility relation on positive integers; it is a quasiorder and a partial order.

- A two-element set with a relation where both elements relate to themselves and to each other yields a quasiorder that is not antisymmetric.

Quasiorders arise in various areas, including algebra, topology (through specialization orders), and computer science (modeling refinement or information ordering).