wikipedia>D.Lazard: more specific link

2023-01-17T19:42:11Z

more specific link

New page

{{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:Prewellordering example svg.svg|thumb|[[Hasse diagram]] of the preorder ''x R y'' defined by ''x''[[integer division|//]]4≤''y''[[integer division|//]]4 on the [[natural numbers]]. Due to the cycles, ''R'' is not anti-symmetric. If all numbers in a cycle are considered equivalent, a partial, even linear, order<ref>on the set of numbers divisible by 4</ref> is obtained. See first example below.]]

In [[mathematics]], especially in [[order theory]], a '''preorder''' or '''quasiorder''' is a [[binary relation]] that is [[reflexive relation|reflexive]] and [[Transitive relation|transitive]]. Preorders are more general than [[equivalence relation]]s and (non-strict) [[partial order]]s, both of which are special cases of a preorder: an [[Antisymmetric relation|antisymmetric]] (or [[Skeleton (category theory)|skeletal]]) preorder is a partial order, and a [[Symmetric relation|symmetric]] preorder is an equivalence relation.

The name {{em|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 relation|asymmetric]]. Because a preorder is a binary relation, the symbol <math>\,\leq\,</math> 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 <math>\,\leq\,</math> 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 <math>a \leq 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 → or <math>\,\lesssim\,</math> is used instead of <math>\,\leq.</math>

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 [[Cycle (graph theory)|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.

==Formal definition==

Consider a [[homogeneous relation]] <math>\,\leq\,</math> on some given [[Set (mathematics)|set]] <math>P,</math> so that by definition, <math>\,\leq\,</math> is some subset of <math>P \times P</math> and the notation <math>a \leq b</math> is used in place of <math>(a, b) \in \,\leq.</math> Then <math>\,\leq\,</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 \leq a</math> for all <math>a \in P,</math> and
#[[Transitive relation|Transitivity]]: if <math>a \leq b \text{ and } b \leq c \text{ then } a \leq 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>
For emphasis or contrast to [[#Strict preorder|strict preorders]], a preorder may also be referred to as a '''non-strict preorder'''.

{{anchor|Strict preorder}}
If reflexivity is replaced with [[Irreflexive relation|irreflexivity]] (while keeping transitivity) then the result is called a strict preorder; explicitly, a '''{{em|strict preorder}}''' on <math>P</math> is a homogeneous binary relation <math>\,<\,</math> on <math>P</math> that satisfies the following conditions:
<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 for all <math>a, b, c \in P.</math></li>
</ol>

A [[binary relation]] is a strict preorder if and only if it is a [[strict partial order]]. By definition, a strict partial order is an [[Asymmetric relation|asymmetric]] strict preorder, where <math>\,<\,</math> is called {{em|asymmetric}} if <math>a for all <math>a, b.</math> Conversely, every strict preorder is a strict partial order because every transitive irreflexive relation is necessarily [[Asymmetric relation|asymmetric]].
Although they are equivalent, the term "strict partial order" is typically preferred over "strict preorder" and readers are referred to the [[Strict partial order|article on strict partial orders]] for details about such relations. In contrast to strict preorders, there are many (non-strict) preorders that are {{em|not}} (non-strict) [[partial order]]s.

=== Related definitions ===

If a preorder is also [[Antisymmetric relation|antisymmetric]], that is, <math>a \leq b</math> and <math>b \leq 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 \leq b</math> implies <math>b \leq a,</math> then it is an [[equivalence relation]].

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

The notion of a preordered set <math>P</math> can be formulated in a [[Category theory|categorical framework]] as a [[thin category]]; that is, as a category with at most one morphism from an object to another. 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. Alternately, a preordered set can be understood as an [[enriched category]], enriched over the category <math>2 = (0 \to 1).</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.

==Examples==
=== Graph theory ===
* (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.

* The [[reachability]] relationship in any [[directed graph]] (possibly containing cycles) gives rise to a preorder, where <math>x \leq 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 \leq 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 in [[graph theory]].

=== 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 \leq 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 |url=https://dl.acm.org/doi/pdf/10.1145/321250.321253}}</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.

=== Other ===
Further examples:
* Every [[finite topological space]] gives rise to a preorder on its points by defining <math>x \leq 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 \leq y</math> if <math>f(x) \leq f(y),</math> where ''f'' is a function into some preorder.
* The relation defined by <math>x \leq 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.
* 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]]. In this sense, categories "generalize" preorders by allowing more than one relation between objects: each morphism is a distinct (named) preorder relation.

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

==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>

==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]].

===Preorders and 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.

===Preorders and strict preorders===

'''Strict preorder induced by a preorder'''

Given a preorder <math>\,\lesssim,</math> a new relation <math>\,<\,</math> can be defined by declaring that <math>a < b</math> if and only if <math>a \lesssim b \text{ and not } 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 
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 
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 

'''Preorders induced by a strict preorder'''

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 (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 "; 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>

==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:Binary relations]]
[[Category:Order theory]]

Preorder - Revision history

Manidh: 1 revision imported

wikipedia>D.Lazard: more specific link

← Older revision	Revision as of 08:58, 16 July 2023
(No difference)