Partial Order

Definition

A partial order on a set $A$ is a relation $\le :A\to A\to \mathrm{Prop}$ that is:

• reflexive: $\forall x:A.x\le x$
• transitive: $\forall x,y,z:A.x\le y\to y\le z\to x\le z$
• anti-symmetric: $\forall x,y:A.x\le y\to y\le x\to x=y$

A set equipped with a partial order is called a partially ordered set or poset.

The strict partial order associated to $\le$ is defined by $x<y⟺x\le y\wedge x\ne y$. The strict relation $<$ is irreflexive, transitive, and asymmetric.

Relationship to Preorders

Every partial order is a preorder; the additional condition is anti-symmetry. Conversely, every preorder $(A,\le )$ induces a partial order on the quotient $A/\sim$, where $x\sim y⟺x\le y\wedge y\le x$.

Examples

• The natural numbers $\mathbb{N}$ with $\le$.
• The power set $\mathcal{P}(X)$ ordered by inclusion $\subseteq$.
• The positive integers ordered by divisibility $m\mid n$.
• The ordinals ordered by $\in$ (membership).

Properties

• A poset $(A,\le )$ may have maximal elements (nothing above them) without having a greatest element (above everything). Similarly for minimal vs. least elements.
• An upper bound for a subset $S\subseteq A$ is an element $u$ with $x\le u$ for all $x\in S$. The supremum (least upper bound) is the smallest such $u$, if it exists.
• A lower bound and infimum (greatest lower bound) are defined dually.
• A complete lattice is a poset in which every subset has a supremum and infimum.

Categorical Perspective

Every partial order $(A,\le )$ is a skeletal thin category: the objects are elements of $A$, and there is exactly one morphism $x\to y$ iff $x\le y$. Skeletal here means no two distinct objects are isomorphic. Order-preserving maps (monotone maps) correspond to functors.

Related Concepts

• Preorder
• Total Ordering
• Well-Ordering
• Complete Lattice
• Reflexive Relation
• Transitive Relation
• Anti-Symmetric Relation
• Thin Category
• Predicate

References

• munkres2000-topology
• https://webspace.maths.qmul.ac.uk/l.h.soicher/designtheory.org/library/encyc/topics/posets.pdf