In mathematics, especially 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, polynomials, or elements of a commutative ring. For example, the divides relation is reflexive as every integer divides itself. But the divides relation is not antisymmetric, because
1
{\displaystyle 1}
divides
−
1
{\displaystyle -1}
and
−
1
{\displaystyle -1}
divides
1
{\displaystyle 1}
. It is to this preorder that "greatest" and "lowest" refer in the phrases "greatest common divisor" and "lowest common multiple" (except that, for integers, the greatest common divisor is also the greatest for the natural order of the integers).
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. 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.
As a binary relation, a preorder may be denoted
≲
{\displaystyle \,\lesssim \,}
or
≤
{\displaystyle \,\leq \,}
. In words, when
a
≲
b
,
{\displaystyle a\lesssim b,}
one may say that b covers a or that a precedes b, or that b reduces to a. Occasionally, the notation ← or → is also used.
View More On Wikipedia.org
