Content deleted Content added
→Examples: placement of 'only' |
Undid revision 1305943583 by 5.45.140.111 (talk) unexplained reduplication of article text |
||
| (38 intermediate revisions by 22 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 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]]:
# [[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>.
A strict partial order is also known as an asymmetric [[strict preorder]].
Line 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 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'' < ''y''}}, or {{nowrap|1=''x'' = ''y''}}, or {{nowrap|''x'' > ''y''}}, or ''x'' and ''y'' are ''incomparable''. This can be represented by a function <math>\text{compare}: P \times P \to \{<,>,=,\vert \}</math> that returns one of four codes when given two elements.<ref>{{cite web |title=Finite posets |url=http://match.stanford.edu/reference/combinat/sage/combinat/posets/posets.html#sage.combinat.posets.posets.FinitePoset.compare_elements |website=Sage 9.2.beta2 Reference Manual: Combinatorics |access-date=5 January 2022|quote=compare_elements(''x'', ''y''): Compare ''x'' and ''y'' in the poset. If {{nowrap|''x'' < ''y''}}, return −1. If {{nowrap|1=''x'' = ''y''}}, return 0. If {{nowrap|''x'' > ''y''}}, return 1. If ''x'' and ''y'' are not comparable, return None.}}</ref><ref>{{cite tech report |last1=Chen |first1=Peter |last2=Ding |first2=Guoli |last3=Seiden |first3=Steve |title=On Poset Merging |page=2 |url=https://www.math.lsu.edu/~ding/poset.pdf |access-date=5 January 2022 |quote=A comparison between two elements s, t in S returns one of three distinct values, namely s≤t, s>t or s<nowiki>|</nowiki>t.}}</ref> This definition is equivalent to a ''partial order on a [[setoid]]'', where equality is taken to be a defined [[equivalence relation]] rather than
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 60:
== Examples ==
[[File:Division relation 4.
Standard examples of posets arising in mathematics include:
Line 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 {{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.
== Partial orders in topological spaces ==
Line 233 ⟶ 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 255 ⟶ 258:
== 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)}}
Line 266 ⟶ 269:
[[Category:Order theory]]
[[Category:Binary relations]]
| |||