In mathematics, especially order theory, a partial order on a 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 orders, in which every pair is comparable. Formally, a partial order is a homogeneous binary relation that is reflexive, antisymmetric, and transitive. A partially ordered set (poset for short) is an ordered pair P = ( X , ≤ ) {\displaystyle P=(X,\leq )} consisting of a set X {\displaystyle X} (called the ground set of P {\displaystyle P} ) and a partial order ≤ {\displaystyle \leq } on X {\displaystyle X} . When the meaning is clear from context and there is no ambiguity about the partial order, the set X {\displaystyle X} itself is sometimes called a poset.
Partial order relations 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, or non-strict partial order, commonly referred to simply as a partial order, is a homogeneous relation ≤ on a set P {\displaystyle P} that is reflexive, antisymmetric, and transitive. That is, for all a , b , c ∈ P , {\displaystyle a,b,c\in P,} it must satisfy:
Reflexivity: a ≤ a {\displaystyle a\leq a} , i.e. every element is related to itself. Antisymmetry: if a ≤ b {\displaystyle a\leq b} and b ≤ a {\displaystyle b\leq a} then a = b {\displaystyle a=b} , i.e. no two distinct elements precede each other. Transitivity: if a ≤ b {\displaystyle a\leq b} and b ≤ c {\displaystyle b\leq c} then a ≤ c {\displaystyle a\leq c} . A non-strict partial order is also known as an antisymmetric preorder.
Strict partial orders An irreflexive, strong, or strict partial order is a homogeneous relation < on a set P {\displaystyle P} that is irreflexive, asymmetric and transitive; that is, it satisfies the following conditions for all a , b , c ∈ P : {\displaystyle a,b,c\in P:}
Irreflexivity: ¬ ( a < a ) {\displaystyle \neg \left(a<a\right)} , i.e. no element is related to itself (also called anti-reflexive). Asymmetry: if a < b {\displaystyle a<b} then not b < a {\displaystyle b<a} . Transitivity: if a < b {\displaystyle a<b} and b < c {\displaystyle b<c} then a < c {\displaystyle a<c} . A transitive relation is asymmetric if and only if it is irreflexive. So the definition is the same if it omits either irreflexivity or asymmetry (but not both). A strict partial order is also known as a strict preorder.
Correspondence of strict and non-strict partial order relations
Strict and non-strict partial orders on a set P {\displaystyle P} are closely related. A non-strict partial order ≤ {\displaystyle \leq } may be converted to a strict partial order by removing all relationships of the form a ≤ a ; {\displaystyle a\leq a;} that is, the strict partial order is the set < := ≤ ∖ Δ P {\displaystyle <\;:=\ \leq \ \setminus \ \Delta _{P}} where Δ P := { ( p , p ) : p ∈ P } {\displaystyle \Delta _{P}:=\{(p,p):p\in P\}} is the identity relation on P × P {\displaystyle P\times P} and ∖ {\displaystyle \;\setminus \;} denotes set subtraction. Conversely, a strict partial order < on P {\displaystyle P} may be converted to a non-strict partial order by adjoining all relationships of that form; that is, ≤ := Δ P ∪ < {\displaystyle \leq \;:=\;\Delta _{P}\;\cup \;<\;} is a non-strict partial order. Thus, if ≤ {\displaystyle \leq } is a non-strict partial order, then the corresponding strict partial order < is the irreflexive kernel given by
… excerpt ends here. Continue reading the full article.
