Content deleted Content added
fmt |
fmt: {{nowrap}} |
||
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 22 ⟶ 21:
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]], and [[Transitive relation|transitive]]; that is, it satisfies the following conditions for all <math>a, b, c \in P:</math>
# [[Irreflexive relation|Irreflexivity]]: not <math>a < a</math>, i.e. no element is related to itself (also called anti-reflexive).▼
# [[Asymmetric relation|Asymmetry]]: if <math>a < b</math> then not <math>b < a</math>.▼
# [[Transitive relation|Transitivity]]: if <math>a < b</math> and <math>b < c</math> then <math>a < c</math>.▼
Irreflexivity and transitivity together imply asymmetry. Also, asymmetry implies irreflexivity. In other words, a transitive relation is asymmetric if and only if it is irreflexive.<ref name="Flaška 2007">{{cite journal |last1=Flaška |first1=V. |last2=Ježek |first2=J. |last3=Kepka |first3=T. |last4=Kortelainen |first4=J. |title=Transitive Closures of Binary Relations I |journal=Acta Universitatis Carolinae. Mathematica et Physica |year=2007 |volume=48 |issue=1 |pages=55–69 |publisher=School of Mathematics
▲#[[Irreflexive relation|Irreflexivity]]: not <math>a < a</math>, i.e. no element is related to itself (also called anti-reflexive).
▲#[[Asymmetric relation|Asymmetry]]: if <math>a < b</math> then not <math>b < a</math>.
▲#[[Transitive relation|Transitivity]]: if <math>a < b</math> and <math>b < c</math> then <math>a < c</math>.
▲Irreflexivity and transitivity together imply asymmetry. Also, asymmetry implies irreflexivity. In other words, a transitive relation is asymmetric if and only if it is irreflexive.<ref name="Flaška 2007">{{cite journal|last1=Flaška|first1=V.|last2=Ježek|first2=J.|last3=Kepka|first3=T.|last4=Kortelainen|first4=J.|title=Transitive Closures of Binary Relations I|journal=Acta Universitatis Carolinae. Mathematica et Physica |year=2007|volume=48 |issue=1 |pages=55–69 |publisher=School of Mathematics - Physics Charles University|___location=Prague|url=http://dml.cz/dmlcz/142762}} Lemma 1.1 (iv). This source refers to asymmetric relations as "strictly antisymmetric".</ref> So the definition is the same if it omits either irreflexivity or asymmetry (but not both).
A strict partial order is also known as an asymmetric [[strict preorder]].
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 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 only be causally affected by ''X'' if {{nowrap|''X'' ≤ ''Y''}}.
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 180 ⟶ 178:
== In category theory ==
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]]''. In differential topology, homology theory (HT) is used for classifying equivalent smooth manifolds M, related to the geometrical shapes of M.
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]]. In differential topology, homology theory (HT) is used for classifying equivalent smooth manifolds M, related to the geometrical shapes of M. In homology theory is given an axiomatic HT approach, especially to singular homology.{{clarify|date=May 2023}} The HT members are algebraic invariants under diffeomorphisms. The axiomatic HT category is taken in G. Kalmbach from the book Eilenberg–Steenrod (see the references) in order to show that the set theoretical topological concept for the HT definition can be extended to partial ordered sets P. Important are chains and filters in P (replacing shapes of M) for defining HT classifications, available for many P applications not related to set theory.
Line 197 ⟶ 195:
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 246 ⟶ 244:
== 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 ⟶ 252:
* {{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|Hasse diagram}}
{{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}}
| |||