Partially ordered set: Difference between revisions

Revision as of 14:52, 25 September 2023

Revision as of 17:30, 13 October 2023

Line 42:

{{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-1514–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.

== 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, \text{</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 strict and non-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.}}</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 54:

== 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 ''x''&nbsp;<&nbsp;''y'', or ''x''&nbsp;=&nbsp;''y'', or ''x''&nbsp;>&nbsp;''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 ''x'' < ''y'', return -1−1. If ''x'' = ''y'', return 0. If ''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 the primitive notion of set equality.<ref>{{cite conference |conference=CALCULEMUS-2003 -– 11th Symposium on the Integration of Symbolic Computation and Mechanized Reasoning|___location=Roma, Italy |date=11 September 2003 |url=https://hal.science/hal-02549766/document#page=98 |publisher=Aracne |language=en|title=Making proofs in a hierarchy of mathematical structures|first1=Virgile|last1=Prevosto|first2=Mathieu|last2=Jaume|pages=89–100}}</ref>

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 75:

* For a set ''X'' and a partially ordered set ''P'', the [[function space]] containing all functions from ''X'' to ''P'', where ''f'' ≤ ''g'' if and only if ''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''}}.

One familiar example of a partially ordered set is a collection of people ordered by [[genealogy|genealogical]] descendancy. Some pairs of people bear the descendant-ancestor relationship, but other pairs of people are incomparable, with neither being a descendant of the other.

Line 104:

=== Sums of partially ordered sets ===

{{anchor|sum}}

Another way to combine two (disjoint) posets is the '''ordinal sum'''<ref>
{{citation

| last1 = Neggers | first1 = J.

| last2 = Kim | first2 = Hee Sik

Line 112 ⟶ 113:

| publisher = World Scientific

| title = Basic Posets

| year = 1998

| year = 1998}}</ref> (or '''linear sum'''),{{sfnp|Davey|Priestley|2002|pp=[https://books.google.com/books?id=vVVTxeuiyvQC&pg=PA17 17–18]}} ''Z'' = ''X'' ⊕ ''Y'', defined on the union of the underlying sets ''X'' and ''Y'' by the order ''a'' ≤_''Z'' ''b'' if and only if:

* ''a'', ''b'' ∈ ''X'' with ''a'' ≤_''X'' ''b'', or

* ''a'', ''b'' ∈ ''Y'' with ''a'' ≤_''Y'' ''b'', or

Line 180 ⟶ 182:

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 hom(''x'', ''y'') = {(''x'', ''y'')} if ''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-SteenrodEilenberg–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.

== Partial orders in topological spaces ==

Line 229 ⟶ 231:

* {{annotated link|Semilattice}}

* {{annotated link|Semiorder}}

* [[Szpilrajn extension theorem]] -– every partial order is contained in some total order.

* {{annotated link|Stochastic dominance}}

* [[Strict weak ordering]] – strict partial order "<" in which the relation {{nowrap|"neither ''a'' < ''b''}} {{nowrap|nor ''b'' < ''a''"}} is transitive.