quasiorder

A quasiorder, also called a preorder, is a binary relation ≤ on a set S that is reflexive and transitive. Reflexivity means every element relates to itself (for all x in S, x ≤ x), and transitivity means that if x ≤ y and y ≤ z, then x ≤ z.

Antisymmetry is not required for a quasiorder, so it is possible that distinct elements satisfy x ≤ y and y ≤ x. Such pairs are considered equivalent under the relation. A simple example is a two-element set {a, b} with a ≤ a, b ≤ b, a ≤ b, and b ≤ a. This is a quasiorder but not a partial order, since a ≠ b yet a ≤ b and b ≤ a.

Associated with a quasiorder is an equivalence relation ~ defined by x ~ y if x ≤ y and y ≤ x. The equivalence classes form a quotient set S/~, and one can define [x] ≤ [y] if x ≤ y to obtain a partial order on S/~. Thus every quasiorder induces a poset on the quotient, while the original elements may collapse together into indistinguishable classes under the quasiorder.

Relation to partial orders: a quasiorder becomes a partial order precisely when antisymmetry holds (x ≤ y and y ≤ x implies x = y).

Examples and usage: the standard ≤ relation on any set is a quasiorder and a partial order. Quasiorders are common in contexts where mutual reachability or mutual refinement is allowed, and they underpin constructions that are later turned into posets via quotienting by the induced equivalence relation.