Content deleted Content added
rt'`9=0894] Tag: Reverted |
Undid revision 1305943583 by 5.45.140.111 (talk) unexplained reduplication of article text |
||
| (10 intermediate revisions by 6 users not shown) | |||
Line 2:
{{Stack|{{Binary relations}}}}
[[Image:Hasse diagram of powerset of 3.svg|right|thumb|upright=1.15|'''Fig. 1''' The [[Hasse diagram]] of the [[Power set|set of all subsets]] of a three-element set <math>\{x, y, z\},</math> ordered by [[set inclusion|inclusion]]. Sets connected by an upward path, like <math>\emptyset</math> and <math>\{x,y\}</math>, are comparable, while e.g. <math>\{x\}</math> and <math>\{y\}</math> are not.]]
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
Formally, a partial order is a [[homogeneous binary relation]] that is [[Reflexive relation|reflexive]], [[antisymmetric relation|antisymmetric]], and [[Transitive relation|transitive]]. A '''partially ordered set''' ('''poset''' for short) is an [[ordered pair]] <math>P=(X,\leq)</math> consisting of a set <math>X</math> (called the ''ground set'' of <math>P</math>) and a partial order <math>\leq</math> on <math>X</math>. When the meaning is clear from context and there is no ambiguity about the partial order, the set <math>X</math> itself is sometimes called a poset.
== Partial order relations ==
{{anchor|Partial order}}The term ''partial order'' usually refers to the reflexive partial order relations, referred to in this article as ''non-strict'' partial orders. However some authors use the term for the other common type of partial order relations, the irreflexive partial order relations, also called strict partial orders. Strict and non-strict partial orders can be put into a [[one-to-one correspondence]], so for every strict partial order there is a unique corresponding non-strict partial order, and vice versa.
=== Partial orders ===
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 35 ⟶ 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 strict relations together, <math>(P,\leq,<)</math>.<ref>{{cite book |last1=Avigad |first1=Jeremy |last2=Lewis |first2=Robert Y. |last3=van Doorn |first3=Floris |title=Logic and Proof |date=29 March 2021 |edition=Release 3.18.4 |url=https://leanprover.github.io/logic_and_proof/relations.html#more-on-orderings |access-date=24 July 2021 |chapter=13.2. More on Orderings |quote=So we can think of every partial order as really being a pair, consisting of a weak partial order and an associated strict one. |archive-date=3 April 2023 |archive-url=https://web.archive.org/web/20230403074506/https://leanprover.github.io/logic_and_proof/relations.html#more-on-orderings |url-status=dead }}</ref>
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 168 ⟶ 177:
== 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]].
| |||