View source for Preorder

{{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.

== Definition ==

Let <math>\,\lesssim\,</math> be a binary relation on a [[Set (mathematics)|set]] <math>P,</math> so that by definition, <math>\,\lesssim\,</math> is some subset of <math>P \times P</math> and the notation <math>a \lesssim b</math> is used in place of <math>(a, b) \in \,\lesssim.</math> Then <math>\,\lesssim\,</math> is called a '''{{em|preorder}}''' or '''{{em|quasiorder}}''' if it is [[Reflexive relation|reflexive]] and [[Transitive relation|transitive]]; that is, if it satisfies:
#[[Reflexive relation|Reflexivity]]: <math>a \lesssim a</math> for all <math>a \in P,</math> and
#[[Transitive relation|Transitivity]]: if <math>a \lesssim b \text{ and } b \lesssim c \text{ then } a \lesssim c</math> for all <math>a, b, c \in P.</math> 

A set that is equipped with a preorder is called a '''preordered set''' (or '''proset''').<ref>For "proset", see e.g. {{citation|last1=Eklund|first1=Patrik|last2=Gähler|first2=Werner|doi=10.1002/mana.19901470123|journal=Mathematische Nachrichten|mr=1127325|pages=219–233|title=Generalized Cauchy spaces|volume=147|year=1990}}.</ref>

==Preorders as partial orders on partitions==

Given a preorder <math>\,\lesssim\,</math> on <math>S</math> one may define an [[equivalence relation]] <math>\,\sim\,</math> on <math>S</math> such that 
<math display=block>a \sim b \quad \text{ if and only if } \quad a \lesssim b \; \text{ and } \; b \lesssim a.</math> 
The resulting relation <math>\,\sim\,</math> is reflexive since the preorder <math>\,\lesssim\,</math> is reflexive; transitive by applying the transitivity of <math>\,\lesssim\,</math> twice; and symmetric by definition. 

Using this relation, it is possible to construct a partial order on the quotient set of the equivalence, <math>S / \sim,</math> which is the set of all [[equivalence class]]es of <math>\,\sim.</math> If the preorder is denoted by <math>R^{+=},</math> then <math>S / \sim</math> is the set of <math>R</math>-[[Cycle (graph theory)|cycle]] equivalence classes: 
<math>x \in [y]</math> if and only if <math>x = y</math> or <math>x</math> is in an <math>R</math>-cycle with <math>y</math>. 
In any case, on <math>S / \sim</math> it is possible to define <math>[x] \leq [y]</math> if and only if <math>x \lesssim y.</math> 
That this is well-defined, meaning that its defining condition does not depend on which representatives of <math>[x]</math> and <math>[y]</math> are chosen, follows from the definition of <math>\,\sim.\,</math> It is readily verified that this yields a partially ordered set.

Conversely, from any partial order on a partition of a set <math>S,</math> it is possible to construct a preorder on <math>S</math> itself. There is a [[one-to-one correspondence]] between preorders and pairs (partition, partial order).

{{em|Example}}: Let <math>S</math> be a [[Theory (mathematical logic)|formal theory]], which is a set of [[Sentence (mathematical logic)|sentences]] with certain properties (details of which can be found in [[Theory (mathematical logic)|the article on the subject]]). For instance, <math>S</math> could be a [[first-order theory]] (like [[Zermelo–Fraenkel set theory]]) or a simpler [[Propositional calculus|zeroth-order theory]]. One of the many properties of <math>S</math> is that it is closed under logical consequences so that, for instance, if a sentence <math>A \in S</math> logically implies some sentence <math>B,</math> which will be written as <math>A \Rightarrow B</math> and also as <math>B \Leftarrow A,</math> then necessarily <math>B \in S</math> (by ''[[modus ponens]]''). 
The relation <math>\,\Leftarrow\,</math> is a preorder on <math>S</math> because <math>A \Leftarrow A</math> always holds and whenever <math>A \Leftarrow B</math> and <math>B \Leftarrow C</math> both hold then so does <math>A \Leftarrow C.</math> 
Furthermore, for any <math>A, B \in S,</math> <math>A \sim B</math> if and only if <math>A \Leftarrow B \text{ and } B \Leftarrow A</math>; that is, two sentences are equivalent with respect to <math>\,\Leftarrow\,</math> if and only if they are [[logically equivalent]]. This particular equivalence relation <math>A \sim B</math> is commonly denoted with its own special symbol <math>A \iff B,</math> and so this symbol <math>\,\iff\,</math> may be used instead of <math>\,\sim.</math> The equivalence class of a sentence <math>A,</math> denoted by <math>[A],</math> consists of all sentences <math>B \in S</math> that are logically equivalent to <math>A</math> (that is, all <math>B \in S</math> such that <math>A \iff B</math>). 
The partial order on <math>S / \sim</math> induced by <math>\,\Leftarrow,\,</math> which will also be denoted by the same symbol <math>\,\Leftarrow,\,</math> is characterized by <math>[A] \Leftarrow [B]</math> if and only if <math>A \Leftarrow B,</math> where the right hand side condition is independent of the choice of representatives <math>A \in [A]</math> and <math>B \in [B]</math> of the equivalence classes. 
All that has been said of <math>\,\Leftarrow\,</math> so far can also be said of its [[converse relation]] <math>\,\Rightarrow.\,</math> 
The preordered set <math>(S, \Leftarrow)</math> is a [[directed set]] because if <math>A, B \in S</math> and if <math>C := A \wedge B</math> denotes the sentence formed by [[logical conjunction]] <math>\,\wedge,\,</math> then <math>A \Leftarrow C</math> and <math>B \Leftarrow C</math> where <math>C \in S.</math> The partially ordered set <math>\left(S / \sim, \Leftarrow\right)</math> is consequently also a directed set. 
See [[Lindenbaum–Tarski algebra]] for a related example.

==Relationship to strict partial orders==

{{anchor|Strict preorder}}
If reflexivity is replaced with [[Irreflexive relation|irreflexivity]] (while keeping transitivity) then we get the definition of a [[strict partial order]] on <math>P</math>. For this reason, the term '''{{em|strict preorder}}''' is sometimes used for a strict partial order. That is, this is a binary relation <math>\,<\,</math> on <math>P</math> that satisfies:
<ol>
<li>[[Irreflexive relation|Irreflexivity]] or anti-reflexivity: {{em|not}} <math>a < a</math> for all <math>a \in P;</math> that is, <math>\,a < a</math> is {{em|false}} for all <math>a \in P,</math> and</li>
<li>[[Transitive relation|Transitivity]]: if <math>a < b \text{ and } b < c \text{ then } a < c</math> for all <math>a, b, c \in P.</math></li>
</ol>

===Strict partial order induced by a preorder===

Any preorder <math>\,\lesssim\,</math> gives rise to a strict partial order defined by <math>a < b</math> if and only if <math>a \lesssim b</math> and not <math>b \lesssim a</math>.
Using the equivalence relation <math>\,\sim\,</math> introduced above, <math>a < b</math> if and only if <math>a \lesssim b \text{ and not } a \sim b;</math> 
and so the following holds
<math display=block>a \lesssim b \quad \text{ if and only if } \quad a < b \; \text{ or } \; a \sim b.</math>
The relation <math>\,<\,</math> is a [[strict partial order]] and {{em|every}} strict partial order can be constructed this way. 
{{em|If}} the preorder <math>\,\lesssim\,</math> is [[Antisymmetric relation|antisymmetric]] (and thus a partial order) then the equivalence <math>\,\sim\,</math> is equality (that is, <math>a \sim b</math> if and only if <math>a = b</math>) and so in this case, the definition of <math>\,<\,</math> can be restated as: 
<math display=block>a < b \quad \text{ if and only if } \quad a \lesssim b \; \text{ and } \; a \neq b \quad\quad (\text{assuming } \lesssim \text{ is antisymmetric}).</math>
But importantly, this new condition is {{em|not}} used as (nor is it equivalent to) the general definition of the relation <math>\,<\,</math> (that is, <math>\,<\,</math> is {{em|not}} defined as: <math>a < b</math> if and only if <math>a \lesssim b \text{ and } a \neq b</math>) because if the preorder <math>\,\lesssim\,</math> is not antisymmetric then the resulting relation <math>\,<\,</math> would not be transitive (consider how equivalent non-equal elements relate). 
This is the reason for using the symbol "<math>\lesssim</math>" instead of the "less than or equal to" symbol "<math>\leq</math>", which might cause confusion for a preorder that is not antisymmetric since it might misleadingly suggest that <math>a \leq b</math> implies <math>a < b \text{ or } a = b.</math> 

===Preorders induced by a strict partial order===

Using the construction above, multiple non-strict preorders can produce the same strict preorder <math>\,<,\,</math> so without more information about how <math>\,<\,</math> was constructed (such knowledge of the equivalence relation <math>\,\sim\,</math> for instance), it might not be possible to reconstruct the original non-strict preorder from <math>\,<.\,</math> Possible (non-strict) preorders that induce the given strict preorder <math>\,<\,</math> include the following:
* Define <math>a \leq b</math> as <math>a < b \text{ or } a = b</math> (that is, take the reflexive closure of the relation). This gives the partial order associated with the strict partial order "<math><</math>" through reflexive closure; in this case the equivalence is equality <math>\,=,</math> so the symbols <math>\,\lesssim\,</math> and <math>\,\sim\,</math> are not needed. 
* Define <math>a \lesssim b</math> as "<math>\text{ not } b < a</math>" (that is, take the inverse complement of the relation), which corresponds to defining <math>a \sim b</math> as "neither <math>a < b \text{ nor } b < a</math>"; these relations <math>\,\lesssim\,</math> and <math>\,\sim\,</math> are in general not transitive; however, if they are then <math>\,\sim\,</math> is an equivalence; in that case "<math><</math>" is a [[strict weak order]]. The resulting preorder is [[Connected relation|connected]] (formerly called total); that is, a [[total preorder]].

If <math>a \leq b</math> then <math>a \lesssim b.</math> 
The converse holds (that is, <math>\,\lesssim\;\; = \;\;\leq\,</math>) if and only if whenever <math>a \neq b</math> then <math>a < b</math> or <math>b < a.</math>

==Examples==

<!--
This example is not from graph theory but it could be explained earlier in the article.
* (see figure above) By ''x''[[integer division|//]]4 is meant the greatest integer that is less than or equal to ''x'' divided by ''4'', thus ''1''[[integer division|//]]4 is ''0'', which is certainly less than or equal to ''0'', which is itself the same as ''0''[[integer division|//]]4.
-->

===Graph theory===

* The [[reachability]] relationship in any [[directed graph]] (possibly containing cycles) gives rise to a preorder, where <math>x \lesssim y</math> in the preorder if and only if there is a path from ''x'' to ''y'' in the directed graph. Conversely, every preorder is the reachability relationship of a directed graph (for instance, the graph that has an edge from ''x'' to ''y'' for every pair {{nowrap|(''x'', ''y'')}} with <math>x \lesssim y</math>). However, many different graphs may have the same reachability preorder as each other. In the same way, reachability of [[directed acyclic graph]]s, directed graphs with no cycles, gives rise to [[partially ordered set]]s (preorders satisfying an additional antisymmetry property).
* The [[graph-minor]] relation is also a preorder.

===Computer science===
In computer science, one can find examples of the following preorders.
* [[Big O notation|Asymptotic order]] causes a preorder over  functions <math>f: \mathbb{N} \to \mathbb{N}</math>. The corresponding equivalence relation is called [[Asymptotic_analysis#Definition|asymptotic equivalence]].
* [[Polynomial-time reduction|Polynomial-time]], [[Many-one reduction|many-one (mapping)]] and [[Turing reduction]]s are preorders on complexity classes.
* [[Subtyping]] relations are usually preorders.<ref>{{cite book |last=Pierce |first=Benjamin C. |author-link=Benjamin C. Pierce
 |date=2002 |title=Types and Programming Languages |title-link=Types and Programming Languages |location=Cambridge, Massachusetts/London, England |publisher=The MIT Press |pages=182ff |isbn=0-262-16209-1}}</ref>
* [[Simulation preorder]]s are preorders (hence the name).
* [[Reduction relation]]s in [[abstract rewriting system]]s.
* The [[encompassment preorder]] on the set of [[term (logic)|term]]s, defined by <math>s \lesssim t</math> if a [[term (logic)#Operations with terms|subterm]] of ''t'' is a [[substitution instance]] of ''s''.
* [[Theta-subsumption]],<ref>{{cite journal |last=Robinson | first=J. A. |title=A machine-oriented logic based on the resolution principle |journal=ACM |volume=12 |number=1 |pages=23–41 |year=1965 | doi=10.1145/321250.321253 | s2cid=14389185 |doi-access=free }}</ref> which is when the literals in a disjunctive first-order formula are contained by another, after applying a [[Substitution (logic)|substitution]] to the former.

===Category theory===

* A [[Category (mathematics)|category]] with at most one [[morphism]] from any object ''x'' to any other object ''y'' is a preorder. Such categories are called [[thin category|thin]]. Here the [[Object (category theory)|objects]] correspond to the elements of <math>P,</math> and there is one morphism for objects which are related, zero otherwise. In this sense, categories "generalize" preorders by allowing more than one relation between objects: each morphism is a distinct (named) preorder relation.
* Alternately, a preordered set can be understood as an [[enriched category]], enriched over the category <math>2 = (0 \to 1).</math>

===Other===
Further examples:
* Every [[finite topological space]] gives rise to a preorder on its points by defining <math>x \lesssim y</math> if and only if ''x'' belongs to every [[Neighborhood (mathematics)|neighborhood]] of ''y''. Every finite preorder can be formed as the [[Specialization (pre)order|specialization preorder]] of a topological space in this way. That is, there is a [[one-to-one correspondence]] between finite topologies and finite preorders. However, the relation between infinite topological spaces and their specialization preorders is not one-to-one.

* A [[net (mathematics)|net]] is a [[directed set|directed]] preorder, that is, each pair of elements has an [[upper bound]].  The definition of convergence via nets is important in [[topology]], where preorders cannot be replaced by [[partially ordered set]]s without losing important features.

* The relation defined by <math>x \lesssim y</math> if <math>f(x) \lesssim f(y),</math> where ''f'' is a function into some preorder.
* The relation defined by <math>x \lesssim y</math> if there exists some [[Injective function|injection]] from ''x'' to ''y''. Injection may be replaced by [[surjection]], or any type of structure-preserving function, such as [[ring homomorphism]], or [[permutation]].
* The [[embedding]] relation for countable [[total order]]ings.

Example of a [[strict weak ordering#Total preorders|total preorder]]:
* [[Preference]], according to common models.

==Constructions==

Every binary relation <math>R</math> on a set <math>S</math> can be extended to a preorder on <math>S</math> by taking the [[transitive closure]] and [[reflexive closure]], <math>R^{+=}.</math>  The transitive closure indicates path connection in <math>R : x R^+ y</math> if and only if there is an <math>R</math>-[[Path (graph theory)|path]] from <math>x</math> to <math>y.</math> 

'''Left residual preorder induced by a binary relation'''

Given a binary relation <math>R,</math> the complemented composition <math>R \backslash R = \overline{R^\textsf{T} \circ \overline{R}}</math> forms a preorder called the [[Heterogeneous relation#Preorder R\R|left residual]],<ref>In this context, "<math>\backslash</math>" does not mean "set difference".</ref> where <math>R^\textsf{T}</math> denotes the [[converse relation]] of <math>R,</math> and <math>\overline{R}</math> denotes the [[Complement (set theory)|complement]] relation of <math>R,</math> while <math>\circ</math> denotes [[relation composition]].

==Related definitions==

If a preorder is also [[Antisymmetric relation|antisymmetric]], that is, <math>a \lesssim b</math> and <math>b \lesssim a</math> implies <math>a = b,</math> then it is a [[Partially ordered set|partial order]].

On the other hand, if it is [[Symmetric relation|symmetric]], that is, if <math>a \lesssim b</math> implies <math>b \lesssim a,</math> then it is an [[equivalence relation]].

A preorder is [[Total preorder|total]] if <math>a \lesssim b</math> or <math>b \lesssim a</math> for all <math>a, b \in P.</math>

A [[preordered class]] is a [[Class (mathematics)|class]] equipped with a preorder. Every set is a class and so every preordered set is a preordered class.

==Uses==
Preorders play a pivotal role in several situations:
* Every preorder can be given a topology, the [[Alexandrov topology]]; and indeed, every preorder on a set is in one-to-one correspondence with an Alexandrov topology on that set.
* Preorders may be used to define [[interior algebra]]s.
* Preorders provide the [[Kripke semantics]] for certain types of [[modal logic]].
* Preorders are used in [[Forcing (mathematics)|forcing]] in [[set theory]] to prove [[consistency]] and [[independence (mathematical logic)|independence]] results.<ref>{{citation
 | last = Kunen | first = Kenneth
 | title = Set Theory, An Introduction to Independence Proofs
 | publisher = Elsevier
 | publication-place = Amsterdam, the Netherlands
 | series = Studies in logic and the foundation of mathematics
 | volume = 102
 | year = 1980
}}.</ref>

==Number of preorders==
{{Number of relations}}

As explained above, there is a 1-to-1 correspondence between preorders and pairs (partition, partial order). Thus the number of preorders is the sum of the number of partial orders on every partition. For example:
{{unordered list
| for <math>n = 3:</math>
* 1 partition of 3, giving 1 preorder
* 3 partitions of {{nowrap|2 + 1}}, giving <math>3 \times 3 = 9</math> preorders
* 1 partition of {{nowrap|1 + 1 + 1}}, giving 19 preorders

I.e., together, 29 preorders.
| for <math>n = 4:</math>
* 1 partition of 4, giving 1 preorder
* 7 partitions with two classes (4 of {{nowrap|3 + 1}} and 3 of {{nowrap|2 + 2}}), giving <math>7 \times 3 = 21</math> preorders
* 6 partitions of {{nowrap|2 + 1 + 1}}, giving <math>6 \times 19 = 114</math> preorders
* 1 partition of {{nowrap|1 + 1 + 1 + 1}}, giving 219 preorders

I.e., together, 355 preorders.
}}

==Interval==
For <math>a \lesssim b,</math> the [[Interval (mathematics)|interval]] <math>[a, b]</math> is the set of points ''x'' satisfying <math>a \lesssim x</math> and <math>x \lesssim b,</math> also written <math>a \lesssim x \lesssim b.</math> It contains at least the points ''a'' and ''b''. One may choose to extend the definition to all pairs <math>(a, b)</math> The extra intervals are all empty.

Using the corresponding strict relation "<math><</math>", one can also define the interval <math>(a, b)</math> as the set of points ''x'' satisfying <math>a < x</math> and <math>x < b,</math> also written <math>a < x < b.</math> An open interval may be empty even if <math>a < b.</math>

Also <math>[a, b)</math> and <math>(a, b]</math> can be defined similarly.

==See also==
* [[Partially ordered set|Partial order]] – preorder that is [[antisymmetric relation|antisymmetric]]
* [[Equivalence relation]] – preorder that is [[Symmetric relation|symmetric]]
* [[Strict weak ordering#Total preorders|Total preorder]] – preorder that is [[connected relation|total]]
* [[Total order]] – preorder that is antisymmetric and total
* [[Directed set]]
* [[Category of preordered sets]]
* [[Prewellordering]]
* [[Well-quasi-ordering]]

== Notes ==
<references />

==References==

* Schmidt, Gunther, "Relational Mathematics", Encyclopedia of Mathematics and its Applications, vol. 132, Cambridge University Press, 2011, {{isbn|978-0-521-76268-7}}
* {{Citation
  | last = Schröder | first = Bernd S. W.
  | title = Ordered Sets: An Introduction
  | place = Boston
  | publisher = Birkhäuser
  | year = 2002
  | isbn = 0-8176-4128-9
  }}

{{Order theory}}

[[Category:Properties of binary relations]]
[[Category:Order theory]]