Partially ordered set: Difference between revisions

Revision as of 07:42, 25 August 2024

Revision as of 01:45, 3 November 2024

Line 17:

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>.

# [[Irreflexive relation|Irreflexivity]]: <math>\neg\left( a < a \right)</math>, i.e. no element is related to itself (also called anti-reflexive).

These two conditions imply:

#* [[Asymmetric relation|Asymmetry]]: if <math>a < b</math> then not <math>b < a</math>.,

Irreflexivitysince if it were true that <math>a < b</math> and transitivity<math>b together< implya</math> asymmetry.then, Alsoby transitivity, asymmetry<math>a<a</math>, implieswhich is forbidden by irreflexivity. InAlternatively, otherone wordscould require only transitivity and asymmetry, since 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]].