Editing Preorder (section)

==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.<ref>{{Citation |last1=Hansson |first1=Sven Ove |title=Preferences |date=2024 |encyclopedia=The Stanford Encyclopedia of Philosophy |editor-last=Zalta |editor-first=Edward N. |url=https://plato.stanford.edu/entries/preferences/ |access-date=2025-03-16 |edition=Winter 2024 |publisher=Metaphysics Research Lab, Stanford University |last2=Grüne-Yanoff |first2=Till |editor2-last=Nodelman |editor2-first=Uri}}</ref>