poset

A partially ordered set, or poset, is a pair (P, ≤) where P is a set and ≤ is a binary relation on P that is reflexive (a ≤ a for all a in P), antisymmetric (if a ≤ b and b ≤ a then a = b), and transitive (if a ≤ b and b ≤ c then a ≤ c). The relation expresses a notion of order that does not require every pair of elements to be comparable.

Examples illustrate the concept: natural numbers with divisibility (a divides b), the power set P(X) with subset inclusion ⊆, and the real numbers with the usual ≤. The latter is a total (or linear) order, a special case of a poset where every pair is comparable.

Key notions include chains and antichains. A chain is a subset in which every pair of elements is comparable, while an antichain is a subset consisting of pairwise incomparable elements. In a Hasse diagram, only the cover relations a ≺ b (with no c such that a ≺ c ≺ b) are drawn, providing a compact graphical representation of the poset.

Extensions and related structures: if every pair of elements has a greatest lower bound (meet) and a least upper bound (join), the poset is a lattice. If every pair is comparable, the poset is a total order. Monotone (order-preserving) functions between posets preserve the order. Posets provide a foundational framework in order theory and relate to lattices, topology, and category theory; a poset can be viewed as a small category with at most one morphism between any two objects.