In mathematics, in particular 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. 1 {\displaystyle 1} divides − 1 {\displaystyle -1} and − 1 {\displaystyle -1} divides 1 {\displaystyle 1} , but − 1 {\displaystyle -1} is not equal to 1 {\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. 4 {\displaystyle 4} and 6 {\displaystyle 6} have the common multiples 24 {\displaystyle 24} , 12 {\displaystyle 12} , 0 {\displaystyle 0} , − 12 {\displaystyle -12} , − 24 {\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 X {\displaystyle X} can equivalently be defined as an equivalence relation on X {\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 \,} .
Definition A binary relation ≲ {\displaystyle \,\lesssim \,} on a set X {\displaystyle X} is called a preorder or quasiorder if it is reflexive and transitive; that is, if it satisfies:
Reflexivity: a ≲ a {\displaystyle a\lesssim a} for all a ∈ X , {\displaystyle a\in X,} and Transitivity: if a ≲ b and b ≲ c then a ≲ c {\displaystyle a\lesssim b{\text{ and }}b\lesssim c{\text{ then }}a\lesssim c} for all a , b , c ∈ X . {\displaystyle a,b,c\in X.}
A set that is equipped with a preorder is called a preordered set (or proset).
Preorders as partial orders on partitions Given a preorder ≲ {\displaystyle \,\lesssim \,} on X {\displaystyle X} one may define an equivalence relation ∼ {\displaystyle \,\sim \,} on X {\displaystyle X} by
… excerpt ends here. Continue reading the full article.
