Content deleted Content added
fmt |
Undid revision 1305943583 by 5.45.140.111 (talk) unexplained reduplication of article text |
||
| (40 intermediate revisions by 23 users not shown) | |||
Line 4:
In [[mathematics]], especially [[order theory]], a '''partial order''' on a [[Set (mathematics)|set]] is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements needs to be comparable; that is, there may be pairs for which neither element precedes the other. Partial orders thus generalize [[total order]]s, in which every pair is comparable.
Formally, a partial order is a [[homogeneous binary relation]] that is [[Reflexive relation|reflexive]], [[
== Partial order relations ==
Line 12:
A '''reflexive''', '''weak''',<ref name=Wallis/> or '''{{visible anchor|non-strict partial order|Non-strict partial order}}''',<ref>{{cite book|chapter=Partially Ordered Sets|title=Mathematical Tools for Data Mining: Set Theory, Partial Orders, Combinatorics|publisher=Springer|year=2008|isbn=9781848002012|chapter-url=https://books.google.com/books?id=6i-F3ZNcub4C&pg=PA127|author1=Simovici, Dan A. |author2=Djeraba, Chabane |name-list-style=amp }}</ref> commonly referred to simply as a '''partial order''', is a [[homogeneous relation]] ≤ on a [[Set (mathematics)|set]] <math>P</math> that is [[Reflexive relation|reflexive]], [[Antisymmetric relation|antisymmetric]], and [[Transitive relation|transitive]]. That is, for all <math>a, b, c \in P,</math> it must satisfy:
# [[Reflexive relation|Reflexivity]]: <math>a \leq a</math>, i.e. every element is related to itself.
# [[Antisymmetric relation|Antisymmetry]]: if <math>a \leq b</math> and <math>b \leq a</math> then <math>a = b</math>, i.e. no two distinct elements precede each other.
Line 21 ⟶ 20:
=== Strict partial orders ===
An '''irreflexive''', '''strong''',<ref name=Wallis/> or '''{{visible anchor|strict partial order|Strict partial order|Irreflexive partial order}}''' is a homogeneous relation < on a set <math>P</math> that is [[Irreflexive relation|irreflexive]], [[Asymmetric relation|asymmetric]]
# [[Irreflexive relation|Irreflexivity]]: <math>\neg\left( a < a \right)</math>, i.e. no element is related to itself (also called anti-reflexive).
# [[
# [[
A strict partial order is also known as an asymmetric [[strict preorder]].
Line 46 ⟶ 44:
== Notation ==
Given a set <math>P</math> and a partial order relation, typically the non-strict partial order <math>\leq</math>, we may uniquely extend our notation to define four partial order relations <math>\leq,</math> <math><,</math> <math>\geq,</math> and <math>></math>, where <math>\leq</math> is a non-strict partial order relation on <math>P</math>, <math> < </math> is the associated strict partial order relation on <math>P</math> (the [[irreflexive kernel]] of <math>\leq</math>), <math>\geq</math> is the dual of <math>\leq</math>, and <math> > </math> is the dual of <math> < </math>. Strictly speaking, the term ''partially ordered set'' refers to a set with all of these relations defined appropriately. But practically, one need only consider a single relation, <math>(P,\leq)</math> or <math>(P,<)</math>, or, in rare instances, the non-strict and
The term ''ordered set'' is sometimes used as a shorthand for ''partially ordered set'', as long as it is clear from the context that no other kind of order is meant. In particular, [[Total order|totally ordered sets]] can also be referred to as "ordered sets", especially in areas where these structures are more common than posets. Some authors use different symbols than <math>\leq</math> such as <math>\sqsubseteq</math><ref>{{cite web |last1=Rounds |first1=William C. |title=Lectures slides |url=http://www.eecs.umich.edu/courses/eecs203-1/203-Mar7.pdf |website=EECS 203: DISCRETE MATHEMATICS |access-date=23 July 2021 |date=7 March 2002}}</ref> or <math>\preceq</math><ref>{{cite book |last1=Kwong |first1=Harris |title=A Spiral Workbook for Discrete Mathematics |date=25 April 2018 |url=https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/A_Spiral_Workbook_for_Discrete_Mathematics_(Kwong)/07%3A_Relations/7.04%3A_Partial_and_Total_Ordering |access-date=23 July 2021 |language=en |chapter=7.4: Partial and Total Ordering}}</ref> to distinguish partial orders from total orders.
Line 54 ⟶ 52:
== Alternative definitions ==
Another way of defining a partial order, found in [[computer science]], is via a notion of [[Comparability|comparison]]. Specifically, given <math>\leq, <, \geq, \text{ and } ></math> as defined previously, it can be observed that two elements ''x'' and ''y'' may stand in any of four [[mutually exclusive]] relationships to each other: either {{nowrap|''x''
Wallis defines a more general notion of a ''partial order relation'' as any [[homogeneous relation]] that is [[Transitive relation|transitive]] and [[Antisymmetric relation|antisymmetric]]. This includes both reflexive and irreflexive partial orders as subtypes.<ref name=Wallis>{{cite book |last1=Wallis |first1=W. D. |title=A Beginner's Guide to Discrete Mathematics |date=14 March 2013 |publisher=Springer Science & Business Media |isbn=978-1-4757-3826-1 |page=100 |url=https://books.google.com/books?id=ONgRBwAAQBAJ&dq=%22partial%20order%20relation%22&pg=PA100 |language=en}}</ref>
Line 62 ⟶ 60:
== Examples ==
[[File:Division relation 4.
Standard examples of posets arising in mathematics include:
Line 73 ⟶ 71:
* The set of [[Linear subspace|subspaces]] of a [[vector space]] ordered by inclusion.
* For a partially ordered set ''P'', the [[sequence space]] containing all [[sequence]]s of elements from ''P'', where sequence ''a'' precedes sequence ''b'' if every item in ''a'' precedes the corresponding item in ''b''. Formally, <math>\left(a_n\right)_{n \in \N} \leq \left(b_n\right)_{n \in \N}</math> if and only if <math>a_n \leq b_n</math> for all <math>n \in \N</math>; that is, a [[componentwise order]].
* For a set ''X'' and a partially ordered set ''P'', the [[function space]] containing all functions from ''X'' to ''P'', where {{nowrap|''f'' ≤ ''g''}} if and only if {{nowrap|''f''(''x'') ≤ ''g''(''x'')}} for all <math>x \in X.</math>
* A [[Fence (mathematics)|fence]], a partially ordered set defined by an alternating sequence of order relations {{nowrap|''a'' < ''b'' > ''c'' < ''d'' ...}}
* The set of events in [[special relativity]] and, in most cases,{{efn|See ''{{slink|General relativity#Time travel}}''.}} [[general relativity]], where for two events ''X'' and ''Y'', {{nowrap|''X'' ≤ ''Y''}} if and only if ''Y'' is in the future [[light cone]] of ''X''. An event ''Y'' can
One familiar example of a partially ordered set is a collection of people ordered by [[genealogy|genealogical]] descendancy. Some pairs of people bear the descendant-ancestor relationship, but other pairs of people are incomparable, with neither being a descendant of the other.
Line 89 ⟶ 87:
| caption2 = '''Fig. 4b''' Product order on <math>\N \times \N</math>
| image3 = Strict product order on pairs of natural numbers.svg|
| caption3 = '''Fig. 4c''' Reflexive closure of strict direct product order on <math>\N \times \N.</math> Elements [[#Formal definition|covered]] by {{nowrap|(3, 3)}} and covering {{nowrap|(3, 3)}} are highlighted in green and red, respectively.
}}
In order of increasing strength, i.e., decreasing sets of pairs, three of the possible partial orders on the [[Cartesian product]] of two partially ordered sets are (see Fig. 4):
* the [[lexicographical order]]: {{nowrap|(''a'', ''b'') ≤ (''c'', ''d'')}} if {{nowrap|''a'' < ''c''}} or ({{nowrap|1=''a'' = ''c''}} and {{nowrap|''b'' ≤ ''d''}});
* the [[product order]]: (''a'', ''b'') ≤ (''c'', ''d'') if ''a'' ≤ ''c'' and ''b'' ≤ ''d'';
* the [[reflexive closure]] of the [[Direct product#Direct product of binary relations|direct product]] of the corresponding strict orders: {{nowrap|(''a'', ''b'') ≤ (''c'', ''d'')}} if ({{nowrap|''a'' < ''c''}} and {{nowrap|''b'' < ''d''}}) or ({{nowrap|1=''a'' = ''c''}} and {{nowrap|1=''b'' = ''d''}}).
All three can similarly be defined for the Cartesian product of more than two sets.
Line 114 ⟶ 112:
| title = Basic Posets
| year = 1998
}}</ref> (or '''linear sum'''),{{sfnp|Davey|Priestley|2002|pp=[https://books.google.com/books?id=vVVTxeuiyvQC&pg=PA17 17–18]}} {{nowrap|1=''Z'' = ''X'' ⊕ ''Y''}}, defined on the union of the underlying sets ''X'' and ''Y'' by the order {{nowrap|''a'' ≤<sub>''Z''</sub> ''b''}} if and only if:
* ''a'', ''b'' ∈ ''X'' with ''a'' ≤<sub>''X''</sub> ''b'', or
* ''a'', ''b'' ∈ ''Y'' with ''a'' ≤<sub>''Y''</sub> ''b'', or
Line 127 ⟶ 125:
The examples use the poset <math>(\mathcal{P}(\{x, y, z\}),\subseteq)</math> consisting of the [[Power set|set of all subsets]] of a three-element set <math>\{x, y, z\},</math> ordered by set inclusion (see Fig. 1).
* ''a'' is ''related to'' ''b'' when ''a'' ≤ ''b''. This does not imply that ''b'' is also related to ''a'', because the relation need not be [[Symmetric relation|symmetric]]. For example, <math>\{x\}</math> is related to <math>\{x, y\},</math> but not the reverse.
* ''a'' and ''b'' are ''[[Comparability|comparable]]'' if {{nowrap|''a'' ≤ ''b''}} or {{nowrap|''b'' ≤ ''a''}}. Otherwise they are ''incomparable''. For example, <math>\{x\}</math> and <math>\{x, y, z\}</math> are comparable, while <math>\{x\}</math> and <math>\{y\}</math> are not.
* A ''[[Totally ordered set|total order]]'' or ''linear order'' is a partial order under which every pair of elements is comparable, i.e. [[Trichotomy (mathematics)|trichotomy]] holds. For example, the natural numbers with their standard order.
* A ''[[Chain (order theory)|chain]]'' is a subset of a poset that is a totally ordered set. For example, <math>\{ \{\,\}, \{x\}, \{x, y, z\} \}</math> is a chain.
* An ''[[antichain]]'' is a subset of a poset in which no two distinct elements are comparable. For example, the set of [[Singleton (mathematics)|singleton]]s <math>\{\{x\}, \{y\}, \{z\}\}.</math>
* An element ''a'' is said to be ''strictly less than'' an element ''b'', if ''a'' ≤ ''b'' and <math>a \neq b.</math> For example, <math>\{x\}</math> is strictly less than <math>\{x, y\}.</math>
* An element ''a'' is said to be ''[[Covering relation|covered]]'' by another element ''b'', written ''a'' ⋖ ''b'' (or ''a'' <: ''b''), if ''a'' is strictly less than ''b'' and no third element ''c'' fits between them; formally: if both ''a'' ≤ ''b'' and <math>a \neq b</math> are true, and ''a'' ≤ ''c'' ≤ ''b'' is false for each ''c'' with <math>a \neq c \neq b.</math> Using the strict order <, the relation ''a'' ⋖ ''b'' can be equivalently rephrased as "{{nowrap|''a'' < ''b''}} but not {{nowrap|''a'' < ''c'' < ''b''}} for any ''c''". For example, <math>\{x\}</math> is covered by <math>\{x, z\},</math> but is not covered by <math>\{x, y, z\}.</math>
=== Extrema ===
Line 172 ⟶ 170:
If the count is made only [[up to]] isomorphism, the sequence 1, 1, 2, 5, 16, 63, 318, ... {{OEIS|A000112}} is obtained.
==
A poset <math>P^*=(X^*, \leq^*)</math> is called a '''subposet''' of another poset <math>P=(X, \leq)</math> provided that <math>X^*</math> is a [[subset]] of <math>X</math> and <math>\leq^*</math> is a subset of <math>\leq</math>. The latter condition is equivalent to the requirement that for any <math>x</math> and <math>y</math> in <math>X^*</math> (and thus also in <math>X</math>), if <math>x \leq^* y</math> then <math>x \leq y</math>.
If <math>P^*</math> is a subposet of <math>P</math> and furthermore, for all <math>x</math> and <math>y</math> in <math>X^*</math>, whenever <math>x \leq y</math> we also have <math>x \leq^* y</math>, then we call <math>P^*</math> the subposet of <math>P</math> '''induced''' by <math>X^*</math>, and write <math>P^* = P[X^*]</math>.
== Linear extension == A partial order <math>\leq^*</math> on a set <math>X</math> is called an '''extension''' of another partial order <math>\leq</math> on <math>X</math> provided that for all elements <math>x, y \in X,</math> whenever <math>x \leq y,</math> it is also the case that <math>x \leq^* y.</math> A [[linear extension]] is an extension that is also a linear (that is, total) order. As a classic example, the lexicographic order of totally ordered sets is a linear extension of their product order. Every partial order can be extended to a total order ([[order-extension principle]]).<ref>{{cite book |last=Jech |first=Thomas |author-link=Thomas Jech |title=The Axiom of Choice |year=2008 |orig-year=1973 |publisher=[[Dover Publications]] |isbn=978-0-486-46624-8}}</ref> In [[computer science]], algorithms for finding linear extensions of partial orders (represented as the [[reachability]] orders of [[directed acyclic graph]]s) are called [[topological sorting]].
== In category theory ==
{{main|Posetal category}}
Every poset (and every [[Preorder|preordered set]]) may be considered as a [[Category (mathematics)|category]] where, for objects <math>x</math> and <math>y,</math> there is at most one [[morphism]] from <math>x</math> to <math>y.</math> More explicitly, let {{nowrap|1=hom(''x'', ''y'') = {{mset|(''x'', ''y'')}}}} if {{nowrap|''x'' ≤ ''y''}} (and otherwise the [[empty set]]) and <math>(y, z) \circ (x, y) = (x, z).</math> Such categories are sometimes called ''[[Posetal category|posetal]]''.
Posets are [[Equivalence of categories|equivalent]] to one another if and only if they are [[Isomorphism of categories|isomorphic]]. In a poset, the smallest element, if it exists, is an [[initial object]], and the largest element, if it exists, is a [[terminal object]]. Also, every preordered set is equivalent to a poset. Finally, every subcategory of a poset is [[isomorphism-closed]].
▲Every poset (and every [[Preorder|preordered set]]) may be considered as a [[Category (mathematics)|category]] where, for objects <math>x</math> and <math>y,</math> there is at most one [[morphism]] from <math>x</math> to <math>y.</math> More explicitly, let hom(''x'', ''y'') = {(''x'', ''y'')} if ''x'' ≤ ''y'' (and otherwise the [[empty set]]) and <math>(y, z) \circ (x, y) = (x, z).</math> Such categories are sometimes called ''[[Posetal category|posetal]]''. In differential topology, homology theory (HT) is used for classifying equivalent smooth manifolds M, related to the geometrical shapes of M.
== Partial orders in topological spaces ==
Line 197 ⟶ 199:
An '''interval''' in a poset ''P'' is a subset that can be defined with interval notation:
* For ''a'' ≤ ''b'', the ''closed interval'' {{closed-closed|''a'', ''b''}} is the set of elements ''x'' satisfying {{nowrap|''a'' ≤ ''x'' ≤ ''b''}} (that is, {{nowrap|''a'' ≤ ''x''}} and {{nowrap|''x'' ≤ ''b''}}). It contains at least the elements ''a'' and ''b''.
* Using the corresponding strict relation "<", the ''open interval'' {{open-open|''a'', ''b''}} is the set of elements ''x'' satisfying {{nowrap|''a'' < ''x'' < ''b''}} (i.e. {{nowrap|''a'' < ''x''}} and {{nowrap|''x'' < ''b''}}). An open interval may be empty even if {{nowrap|''a'' < ''b''}}. For example, the open interval {{open-open|0, 1}} on the integers is empty since there is no integer {{mvar|x}} such that {{math|0 < {{var|x}} < 1}}.
* The ''half-open intervals'' {{closed-open|''a'', ''b''}} and {{open-closed|''a'', ''b''}} are defined similarly.
Whenever {{nowrap|''a'' ≤ ''b''}} does not hold, all these intervals are empty. Every interval is a convex set, but the converse does not hold; for example, in the poset of divisors of 120, ordered by divisibility (see Fig. 7b), the set {{mset|1, 2, 4, 5, 8}} is convex, but not an interval.
An interval {{mvar|I}} is bounded if there exist elements <math>a, b \in P</math> such that {{math|{{var|I}} ⊆ {{closed-closed|''a'', ''b''}}}}. Every interval that can be represented in interval notation is obviously bounded, but the converse is not true. For example, let {{math|1=''P'' = {{open-open|0, 1}} ∪ {{open-open|1, 2}} ∪ {{open-open|2, 3}}}} as a subposet of the real numbers. The subset {{open-open|1, 2}} is a bounded interval, but it has no [[infimum]] or [[supremum]] in ''P'', so it cannot be written in interval notation using elements of ''P''.
Line 235 ⟶ 237:
* [[Strict weak ordering]] – strict partial order "<" in which the relation {{nowrap|"neither ''a'' < ''b''}} {{nowrap|nor ''b'' < ''a''"}} is transitive.
* {{annotated link|Total order}}
* {{annotated link|Zorn's lemma}}
{{div col end}}
Line 246 ⟶ 247:
== References ==
{{refbegin}}
* {{cite book |last1=Davey |first1=B. A. |last2=Priestley |first2=H. A. |title=Introduction to Lattices and Order |edition=2nd |___location=New York |publisher=Cambridge University Press |year=2002 |isbn=978-0-521-78451-1 |title-link= Introduction to Lattices and Order}}
* {{Cite journal|first=Jayant V. |last=Deshpande|title=On Continuity of a Partial Order|journal=Proceedings of the American Mathematical Society|volume=19|year=1968|pages=383–386|issue=2 |doi=10.1090/S0002-9939-1968-0236071-7 |doi-access= free}}
Line 253 ⟶ 255:
* {{cite book|first=S.|last=Eilenberg|author-link=N. Steenrod|title=Foundations of Algebraic Topology|publisher=Princeton University Press|year=2016}}
* {{cite journal|first=G.|last=Kalmbach|title=Extension of Homology Theory to Partially Ordered Sets|journal=J. Reine Angew. Math.|volume=280|year=1976|pages=134–156}}
{{refend}}
== External links ==
{{Commons category inline|Hasse diagrams}}; each of which shows an example for a partial order
{{refbegin}}
* {{OEIS el|1=A001035|2= Number of posets with ''n'' labeled elements|formalname=Number of partially ordered sets ("posets") with n labeled elements (or labeled acyclic transitive digraphs)}}
* {{OEIS el|1=A000112|2=Number of partially ordered sets ("posets") with n unlabeled elements.}}
{{refend}}
{{Order theory}}
Line 264 ⟶ 269:
[[Category:Order theory]]
[[Category:Binary relations]]
| |||