|
|
| (706 intermediate revisions by more than 100 users not shown) |
| Line 1: |
Line 1: |
| {{About|the binary relation|the graph vertex ordering|Depth-first search|other uses}}
| | This is a preview for the new '''MathML rendering mode''' (with SVG fallback), which is availble in production for registered users. |
|
| |
|
| In [[mathematics]], especially in [[order theory]], a '''preorder''' or '''quasi-order''' is a [[binary relation]] that is [[reflexive relation|reflexive]] and [[transitive relation|transitive]]. All [[partial order]]s and [[equivalence relation]]s are preorders, but preorders are more general.
| | If you would like use the '''MathML''' rendering mode, you need a wikipedia user account that can be registered here [[https://en.wikipedia.org/wiki/Special:UserLogin/signup]] |
| | * Only registered users will be able to execute this rendering mode. |
| | * Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere. |
|
| |
|
| The name 'preorder' comes from the idea that preorders are 'almost' (partial) orders, but not quite; they're neither [[anti-symmetric relation|anti-symmetric]] nor [[symmetric relation|symmetric]]. Because a preorder is a binary relation, the symbol ≤ can be used as the notational device for the relation. However, because they are not anti-symmetric, some of the ordinary intuition that a student may have with regards to the symbol ≤ may not apply. On the other hand, a pre-order can be used, in a straightforward fashion, to define a partial order and an equivalence relation. Doing so, however, is not always useful or worth-while, depending on the problem domain being studied.
| | Registered users will be able to choose between the following three rendering modes: |
|
| |
|
| In words, when ''a'' ≤ ''b'', one may say that ''b'' ''covers'' ''a'' or that ''b'' ''precedes'' ''a'', or that ''b'' ''reduces'' to ''a''. Occasionally, the notation ← or <math>\lesssim</math> is used instead of ≤.
| | '''MathML''' |
| | :<math forcemathmode="mathml">E=mc^2</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. Note that, in general, the corresponding graphs may be [[cyclic graph]]s: preorders may have cycles in them. 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 may have many disconnected components. The [[diamond lemma]] is an important result for certain kinds of preorders.
| | <!--'''PNG''' (currently default in production) |
| | :<math forcemathmode="png">E=mc^2</math> |
|
| |
|
| Many order theoretical definitions for partially ordered sets can be generalized to preorders, but the extra effort of generalization is rarely needed.{{Citation needed|date=July 2010}}
| | '''source''' |
| | :<math forcemathmode="source">E=mc^2</math> --> |
|
| |
|
| ==Formal definition== | | <span style="color: red">Follow this [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering link] to change your Math rendering settings.</span> You can also add a [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering-skin Custom CSS] to force the MathML/SVG rendering or select different font families. See [https://www.mediawiki.org/wiki/Extension:Math#CSS_for_the_MathML_with_SVG_fallback_mode these examples]. |
|
| |
|
| Consider some [[Set (mathematics)|set]] ''P'' and a [[binary relation]] ≤ on ''P''. Then ≤ is a '''preorder''', or '''quasiorder''', if it is [[reflexive relation|reflexive]] and [[transitive relation|transitive]], i.e., for all ''a'', ''b'' and ''c'' in ''P'', we have that:
| | ==Demos== |
|
| |
|
| :''a'' ≤ ''a'' (reflexivity) | | Here are some [https://commons.wikimedia.org/w/index.php?title=Special:ListFiles/Frederic.wang demos]: |
| : if ''a'' ≤ ''b'' and ''b'' ≤ ''c'' then ''a'' ≤ ''c'' (transitivity) | |
|
| |
|
| ''Note that an alternate definition of preorder requires the relation to be [[irreflexive relation|irreflexive]]. However, as this article is examining preorders as a logical extension of non-strict partial orders, the current definition is more intuitive.''
| |
|
| |
|
| A set that is equipped with a preorder is called a '''preordered set''' (or '''proset''').
| | * accessibility: |
| | ** Safari + VoiceOver: [https://commons.wikimedia.org/wiki/File:VoiceOver-Mac-Safari.ogv video only], [[File:Voiceover-mathml-example-1.wav|thumb|Voiceover-mathml-example-1]], [[File:Voiceover-mathml-example-2.wav|thumb|Voiceover-mathml-example-2]], [[File:Voiceover-mathml-example-3.wav|thumb|Voiceover-mathml-example-3]], [[File:Voiceover-mathml-example-4.wav|thumb|Voiceover-mathml-example-4]], [[File:Voiceover-mathml-example-5.wav|thumb|Voiceover-mathml-example-5]], [[File:Voiceover-mathml-example-6.wav|thumb|Voiceover-mathml-example-6]], [[File:Voiceover-mathml-example-7.wav|thumb|Voiceover-mathml-example-7]] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-Audio-Windows7-InternetExplorer.ogg Internet Explorer + MathPlayer (audio)] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-SynchronizedHighlighting-WIndows7-InternetExplorer.png Internet Explorer + MathPlayer (synchronized highlighting)] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-Braille-Windows7-InternetExplorer.png Internet Explorer + MathPlayer (braille)] |
| | ** NVDA+MathPlayer: [[File:Nvda-mathml-example-1.wav|thumb|Nvda-mathml-example-1]], [[File:Nvda-mathml-example-2.wav|thumb|Nvda-mathml-example-2]], [[File:Nvda-mathml-example-3.wav|thumb|Nvda-mathml-example-3]], [[File:Nvda-mathml-example-4.wav|thumb|Nvda-mathml-example-4]], [[File:Nvda-mathml-example-5.wav|thumb|Nvda-mathml-example-5]], [[File:Nvda-mathml-example-6.wav|thumb|Nvda-mathml-example-6]], [[File:Nvda-mathml-example-7.wav|thumb|Nvda-mathml-example-7]]. |
| | ** Orca: There is ongoing work, but no support at all at the moment [[File:Orca-mathml-example-1.wav|thumb|Orca-mathml-example-1]], [[File:Orca-mathml-example-2.wav|thumb|Orca-mathml-example-2]], [[File:Orca-mathml-example-3.wav|thumb|Orca-mathml-example-3]], [[File:Orca-mathml-example-4.wav|thumb|Orca-mathml-example-4]], [[File:Orca-mathml-example-5.wav|thumb|Orca-mathml-example-5]], [[File:Orca-mathml-example-6.wav|thumb|Orca-mathml-example-6]], [[File:Orca-mathml-example-7.wav|thumb|Orca-mathml-example-7]]. |
| | ** From our testing, ChromeVox and JAWS are not able to read the formulas generated by the MathML mode. |
|
| |
|
| If a preorder is also [[antisymmetric relation|antisymmetric]], that is, ''a'' ≤ ''b'' and ''b'' ≤ ''a'' implies ''a'' = ''b'', then it is a [[partially ordered set|partial order]].
| | ==Test pages == |
|
| |
|
| On the other hand, if it is [[symmetric relation|symmetric]], that is, if ''a'' ≤ ''b'' implies ''b'' ≤ ''a'', then it is an [[equivalence relation]].
| | To test the '''MathML''', '''PNG''', and '''source''' rendering modes, please go to one of the following test pages: |
| | *[[Displaystyle]] |
| | *[[MathAxisAlignment]] |
| | *[[Styling]] |
| | *[[Linebreaking]] |
| | *[[Unique Ids]] |
| | *[[Help:Formula]] |
|
| |
|
| A preorder which is preserved in all contexts (i.e. respected by all functions on ''P'') is called a '''precongruence'''.
| | *[[Inputtypes|Inputtypes (private Wikis only)]] |
| A precongruence which is also [[symmetric relation|symmetric]] (i.e. is an [[equivalence relation]]) is a [[congruence relation]].
| | *[[Url2Image|Url2Image (private Wikis only)]] |
| | | ==Bug reporting== |
| Equivalently, a preordered set ''P'' can be defined as a [[category theory|category]] with [[object (category theory)|objects]] the elements of ''P'', and each [[hom-set]] having at most one element (one for objects which are related, zero otherwise).
| | If you find any bugs, please report them at [https://bugzilla.wikimedia.org/enter_bug.cgi?product=MediaWiki%20extensions&component=Math&version=master&short_desc=Math-preview%20rendering%20problem Bugzilla], or write an email to math_bugs (at) ckurs (dot) de . |
| | |
| Alternately, a preordered set can be understood as an [[enriched category]], enriched over the category '''2''' = (0→1).
| |
| | |
| ==Examples== | |
| * The [[reachability]] relationship in any [[directed graph]] (possibly containing cycles) gives rise to a preorder, where ''x'' ≤ ''y'' 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 (''x'', ''y'') with ''x'' ≤ ''y''). 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 anti-symmetry property).
| |
| * Every [[finite topological space]] gives rise to a preorder on its points, in which ''x'' ≤ ''y'' if and only if ''x'' belongs to every neighborhood of ''y'', and 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 [[bijection|1-to-1 correspondence]] between finite topologies and finite preorders. However, the relation between infinite topological spaces and their specialization preorders is not 1-to-1.
| |
| * 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 \le y</math> [[iff]] <math>f(x) \le f(y)</math>, where ''f'' is a function into some preorder.
| |
| * The relation defined by <math>x \le y</math> [[iff]] 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.
| |
| * The [[graph-minor]] relation in [[graph theory]].
| |
| * A [[category (mathematics)|category]] with at most one [[morphism]] between any pair of objects 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.
| |
| | |
| In computer science, one can find examples of the following preorders.
| |
| * The [[Subtype|subtyping]] relations are usually preorders.
| |
| * [[Simulation preorder]]s are preorders (hence the name).
| |
| * [[Reduction relation]]s in [[abstract rewriting system]]s.
| |
| | |
| 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]].
| |
| | |
| ==Constructions==
| |
| | |
| Every binary relation R on a set S can be extended to a preorder on S by taking the [[transitive closure]] and [[Binary relation#Operations on binary relations|reflexive closure]], R<sup>+=</sup>. The transitive closure indicates path connection in R: ''x'' R<sup>+</sup> ''y'' if and only if there is an R-[[Path (graph theory)|path]] from ''x'' to y.
| |
| | |
| Given a preorder <math>\lesssim</math> on S one may define an [[equivalence relation]] ~ on S such that ''a'' ~ ''b'' if and only if ''a'' <math>\lesssim</math> ''b'' and ''b'' <math>\lesssim</math> ''a''. (The resulting relation is reflexive since a preorder is reflexive, transitive by applying transitivity of the preorder twice, and symmetric by definition.)
| |
| | |
| Using this relation, it is possible to construct a partial order on the quotient set of the equivalence, S / ~, the set of all [[equivalence class]]es of ~. Note that if the preorder is R<sup>+=</sup>, S / ~ is the set of R-[[Cycle (graph theory)|cycle]] equivalence classes: ''x'' ∈ [''y''] if and only if ''x'' = ''y'' or ''x'' is in an R-cycle with y. In any case, on S / ~ we can define [''x''] ≤ [''y''] if and only if ''x'' <math>\lesssim</math> ''y''. By the construction of ~, this definition is independent of the chosen representatives and the corresponding relation is indeed well-defined. It is readily verified that this yields a partially ordered set.
| |
| | |
| Conversely, from a partial order on a partition of a set S one can construct a preorder on S. There is a 1-to-1 correspondence between preorders and pairs (partition, partial order).
| |
| | |
| For a preorder "<math>\lesssim</math>", a relation "<" can be defined as ''a'' < ''b'' if and only if (''a'' <math>\lesssim</math> ''b'' and not ''b'' <math>\lesssim</math> ''a''), or equivalently, using the equivalence relation introduced above, (''a'' <math>\lesssim</math> ''b'' and not ''a'' ~ ''b''). It is a [[strict partial order]]; every strict partial order can be the result of such a construction. If the preorder is anti-symmetric, hence a partial order "≤", the equivalence is equality, so the relation "<" can also be defined as ''a'' < ''b'' if and only if (''a'' ≤ ''b'' and ''a'' ≠ ''b'').
| |
| | |
| (Alternatively, for a preorder "<math>\lesssim</math>", a relation "<" can be defined as ''a'' < ''b'' if and only if (''a'' <math>\lesssim</math> ''b'' and ''a'' ≠ ''b''). The result is the reflexive reduction of the preorder. However, if the preorder is not anti-symmetric the result is not transitive, and if it is, as we have seen, it is the same as before.)
| |
| | |
| Conversely we have ''a'' <math>\lesssim</math> ''b'' if and only if ''a'' < ''b'' or ''a'' ~ ''b''. This is the reason for using the notation "<math>\lesssim</math>"; "≤" can be confusing for a preorder that is not anti-symmetric, it may suggest that ''a'' ≤ ''b'' implies that ''a'' < ''b'' or ''a'' = ''b''.
| |
| | |
| Note that with this construction multiple preorders "<math>\lesssim</math>" can give the same relation "<", so without more information, such as the equivalence relation, "<math>\lesssim</math>" cannot be reconstructed from "<". Possible preorders include the following:
| |
| *Define ''a'' ≤ ''b'' as ''a'' < ''b'' or ''a'' = ''b'' (i.e., take the reflexive closure of the relation). This gives the partial order associated with the strict partial order "<" through reflexive closure; in this case the equivalence is equality, so we don't need the notations <math>\lesssim</math> and ~.
| |
| *Define ''a'' <math>\lesssim</math> ''b'' as "not ''b'' < ''a''" (i.e., take the inverse complement of the relation), which corresponds to defining ''a'' ~ ''b'' as "neither ''a'' < ''b'' nor ''b'' < ''a''"; these relations <math>\lesssim</math> and ~ are in general not transitive; however, if they are, ~ is an equivalence; in that case "<" is a [[strict weak order]]. The resulting preorder is [[total relation|total]], that is, a [[total preorder]].
| |
| | |
| ==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:
| |
| *for n=3:
| |
| **1 partition of 3, giving 1 preorder
| |
| **3 partitions of 2+1, giving 3 × 3 = 9 preorders
| |
| **1 partition of 1+1+1, giving 19 preorders
| |
| :i.e. together 29 preorders.
| |
| *for n=4:
| |
| **1 partition of 4, giving 1 preorder
| |
| **7 partitions with two classes (4 of 3+1 and 3 of 2+2), giving 7 × 3 = 21 preorders
| |
| **6 partitions of 2+1+1, giving 6 × 19 = 114 preorders
| |
| **1 partition of 1+1+1+1, giving 219 preorders
| |
| :i.e. together 355 preorders.
| |
| | |
| ==Interval==
| |
| For ''a'' <math>\lesssim</math> ''b'', the [[interval (mathematics)|interval]] [''a'',''b''] is the set of points ''x'' satisfying ''a'' <math>\lesssim</math> ''x'' and ''x'' <math>\lesssim</math> ''b'', also written ''a'' <math>\lesssim</math> ''x'' <math>\lesssim</math> ''b''. It contains at least the points ''a'' and ''b''. One may choose to extend the definition to all pairs (''a'',''b''). The extra intervals are all empty.
| |
| | |
| Using the corresponding strict relation "<", one can also define the interval (''a'',''b'') as the set of points ''x'' satisfying ''a'' < ''x'' and ''x'' < ''b'', also written ''a'' < ''x'' < ''b''. An open interval may be empty even if ''a'' < ''b''.
| |
| | |
| Also [''a'',''b'') and (''a'',''b''] 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 [[Total relation|total]]
| |
| *[[total order]] - preorder that is antisymmetric and total
| |
| *[[directed set]]
| |
| *[[category of preordered sets]]
| |
| *[[prewellordering]]
| |
| *[[preordered class]]
| |
| *[[Well-quasi-ordering]]
| |
| *[[Newman's lemma]]
| |
| | |
| ==References==
| |
| {{refbegin}}
| |
| * {{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}}
| |
| {{refend}}
| |
| | |
| [[Category:Order theory]]
| |
| [[Category:Mathematical relations]]
| |
| | |
| [[cs:Kvaziuspořádání]]
| |
| [[da:Præordning]]
| |
| [[de:Quasiordnung]]
| |
| [[es:Conjunto preordenado]]
| |
| [[fr:Pré-ordre]]
| |
| [[it:Preordine]]
| |
| [[he:קדם סדר]]
| |
| [[pl:Praporządek]]
| |
| [[ru:Предпорядок]]
| |
| [[sk:Kváziusporiadanie]]
| |
| [[uk:Передпорядок]]
| |
| [[zh:预序关系]]
| |
