|
== 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 == 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.
# [[Transitive relation|Transitivity]]: if <math>a \leq b </math> and <math>b \leq c</math> then <math>a \leq c</math>.
A non-strict partial order is also known as an antisymmetric [[preorder]].
=== 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]] and [[Transitive relation|transitive]]; that is, it satisfies the following conditions for all <math>a, b, c \in P:</math>
# [[Irreflexive relation|Irreflexivity]]: <math>\neg\left( a < a \right)</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>.
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]].
=== Correspondence of strict and non-strict partial order relations ===
[[File:PartialOrders redundencies svg.svg|thumb|upright=1.25|'''Fig. 2''' [[Commutative diagram]] about the connections between strict/non-strict relations and their duals, via the operations of reflexive closure (''cls''), irreflexive kernel (''ker''), and converse relation (''cnv''). Each relation is depicted by its [[logical matrix]] for the poset whose [[Hasse diagram]] is depicted in the center. For example <math>3 \not\leq 4</math> so row 3, column 4 of the bottom left matrix is empty.]]
Strict and non-strict partial orders on a set <math>P</math> are closely related. A non-strict partial order <math>\leq</math> may be converted to a strict partial order by removing all relationships of the form <math>a \leq a;</math> that is, the strict partial order is the set <math>< \; := \ \leq\ \setminus \ \Delta_P</math> where <math>\Delta_P := \{ (p, p) : p \in P \}</math> is the [[identity relation]] on <math>P \times P</math> and <math>\;\setminus\;</math> denotes [[set subtraction]]. Conversely, a strict partial order < on <math>P</math> may be converted to a non-strict partial order by adjoining all relationships of that form; that is, <math>\leq\; := \;\Delta_P\; \cup \;<\;</math> is a non-strict partial order. Thus, if <math>\leq</math> is a non-strict partial order, then the corresponding strict partial order < is the [[irreflexive kernel]] given by
<math display=block>a < b \text{ if } a \leq b \text{ and } a \neq b.</math>
Conversely, if < is a strict partial order, then the corresponding non-strict partial order <math>\leq</math> is the [[reflexive closure]] given by:
<math display=block>a \leq b \text{ if } a < b \text{ or } a = b.</math>
=== Dual orders ===
{{Main|Duality (order theory)}}
The ''dual'' (or ''opposite'') <math>R^{\text{op}}</math> of a partial order relation <math>R</math> is defined by letting <math>R^{\text{op}}</math> be the [[converse relation]] of <math>R</math>, i.e. <math>x R^{\text{op}} y</math> if and only if <math>y R x</math>. The dual of a non-strict partial order is a non-strict partial order,{{sfnp|Davey|Priestley|2002|pp=[https://books.google.com/books?id=vVVTxeuiyvQC&pg=PA14 14–15]}} and the dual of a strict partial order is a strict partial order. The dual of a dual of a relation is the original relation. 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 ===
| 