Partially ordered set: Difference between revisions

Revision as of 19:53, 22 June 2024

Latest revision as of 02:03, 15 August 2025

(25 intermediate revisions by 16 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]], [[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 ==

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

Irreflexivity and transitivity together imply asymmetry. Also, asymmetry implies irreflexivity. In other words, aA 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]].

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

== Examples ==

[[File:Division relation 4.pngsvg|thumb|alt=Division Relationship Up to 4|'''Fig. 3''' Graph of the divisibility of numbers from 1 to 4. This set is partially, but not totally, ordered because there is a relationship from 1 to every other number, but there is no relationship from 2 to 3 or 3 to 4]]

Standard examples of posets arising in mathematics include:

Line 258:

== External links ==

{{Commons category inline|Hasse diagrams}}; each of which shows an example for a partial order

{{Commons|Hasse diagram}}

{{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 269:

[[Category:Order theory]]

[[Category:Binary relations]]

[[de:Ordnungsrelation#Halbordnung]]