Editing Preorder (section)

{{short description|Reflexive and transitive binary relation}}
{{About|binary relations|the graph vertex ordering|depth-first search|purchase orders for unreleased products|pre-order|other uses}}
{{Redirect|Quasiorder|irreflexive transitive relations|strict order}}

{{stack|{{Binary relations}}}}

[[File:Preorder.png|thumb|[[Hasse diagram]] of the preorder ''x R y'' defined by ''x''[[integer division|//]]4≤''y''[[integer division|//]]4 on the [[natural numbers]]. Equivalence classes (sets of elements such that ''x R y'' and ''y R x'') are shown together as a single node. The relation on equivalence classes is a [[partial order]].]]

In [[mathematics]], especially in [[order theory]], a '''preorder''' or '''quasiorder''' is a [[binary relation]] that is [[reflexive relation|reflexive]] and [[Transitive relation|transitive]]. The name {{em|preorder}} is meant to suggest that preorders are ''almost'' [[partial order]]s, but not quite, as they are not necessarily [[Antisymmetric relation|antisymmetric]].

A natural example of a preorder is the [[Divisor#Definition|divides relation]] "x divides y" between integers, [[polynomial]]s, 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 <math>1</math> divides <math>-1</math> and <math>-1</math> divides <math>1</math>. 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 relation]]s and (non-strict) partial orders. Both of these are special cases of a preorder: an antisymmetric preorder is a partial order, and a [[Symmetric relation|symmetric]] preorder is an equivalence relation. Moreover, a preorder on a set <math>X</math> can equivalently be defined as an equivalence relation on <math>X</math>, 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 relation|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 <math>\,\lesssim\,</math> or <math>\,\leq\,</math>. In words, when <math>a \lesssim b,</math> one may say that ''b'' {{em|covers}} ''a'' or that ''a'' {{em|precedes}} ''b'', or that ''b'' {{em|reduces}} to ''a''. Occasionally, the notation ← or → is also used.