Preorder

In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special cases of a preorder. An antisymmetric preorder is a partial order, and a symmetric preorder is an equivalence relation. In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special cases of a preorder. An antisymmetric preorder is a partial order, and a symmetric preorder is an equivalence relation. The name preorder comes from the idea that preorders (that are not partial orders) are 'almost' (partial) orders, but not quite; they are neither necessarily antisymmetric nor asymmetric. Because a preorder is a binary relation, the symbol ≤ can be used as the notational device for the relation. However, because they are not necessarily antisymmetric, some of the ordinary intuition associated to the symbol ≤ may not apply. On the other hand, a preorder can be used, in a straightforward fashion, to define a partial order and an equivalence relation. Doing so, however, is not always useful or worthwhile, depending on the problem domain being studied. In words, when a ≤ b, one may say that b covers a or that a precedes b, or that b reduces to a. Occasionally, the notation ← or ≲ is used instead of ≤. To every preorder, there corresponds 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. In general, the corresponding graphs may contain cycles. 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. Consider some set P and a binary relation ≤ on P. Then ≤ is a preorder, or quasiorder, if it is reflexive and transitive; i.e., for all a, b and c in P, we have that: A set that is equipped with a preorder is called a preordered set (or proset). If a preorder is also antisymmetric, that is, a ≤ b and b ≤ a implies a = b, then it is a partial order. On the other hand, if it is symmetric, that is, if a ≤ b implies b ≤ a, then it is an equivalence relation. A preorder is total if either a ≤ b or b ≤ a for all a, b.