Partially ordered set

A partially ordered set, commonly abbreviated as a poset, is a set equipped with a binary relation that expresses a consistent but not necessarily total notion of precedence. Unlike a total order, a partial order permits pairs of elements for which neither precedes the other. This distinction allows partially ordered sets to represent hierarchical inclusion, logical implication, divisibility, dependency, and other relations in which universal comparability is absent.

Formally, a partially ordered set is an ordered pair

[ (P,\leq), ]

where (P) is a set and (\leq) is a binary relation on (P) satisfying reflexivity, antisymmetry, and transitivity. Reflexivity means that (x\leq x) for every (x\in P). Antisymmetry means that (x\leq y) and (y\leq x) together imply (x=y). Transitivity means that (x\leq y) and (y\leq z) imply (x\leq z).

The notation (\leq) does not require the elements of (P) to be numbers, nor does it require the relation to be numerical comparison. It is conventional notation for any relation satisfying the three order axioms.

Strict and non-strict formulations

Every partial order (\leq) determines a strict partial order (<) through

[ x<y \quad\Longleftrightarrow\quad x\leq y\text{ and }x\neq y. ]

The resulting strict relation is irreflexive and transitive. It is also asymmetric, since (x<y) excludes (y<x). Conversely, an irreflexive transitive relation determines a non-strict partial order by adjoining equality:

[ x\leq y \quad\Longleftrightarrow\quad x<y\text{ or }x=y. ]

The strict and non-strict formulations therefore contain the same order-theoretic information. Their difference is primarily notational, although particular arguments may be expressed more compactly in one formulation.

A preorder satisfies reflexivity and transitivity but not necessarily antisymmetry. Every preorder induces a partial order on equivalence classes under the relation

[ x\sim y \quad\Longleftrightarrow\quad x\leq y\text{ and }y\leq x. ]

This quotient construction separates genuine ordering information from distinctions that the preorder itself cannot detect.

Comparability and internal structure

Two elements (x,y\in P) are comparable when either (x\leq y) or (y\leq x). They are incomparable when neither relation holds. A partial order becomes a total order precisely when every pair of elements is comparable.

A subset (C\subseteq P) is a chain when every two elements of (C) are comparable. The order inherited by a chain is total. A subset (A\subseteq P) is an antichain when distinct elements of (A) are always incomparable. Chains describe totally ordered regions within a poset, whereas antichains describe collections whose members have no order relation among themselves.

An element (m\in P) is minimal when no distinct element lies strictly below it. An element (M\in P) is maximal when no distinct element lies strictly above it. A least element is below every element of the poset, while a greatest element is above every element. Least and greatest elements, when they exist, are unique. Minimal and maximal elements need not be unique, because several mutually incomparable elements can occupy the corresponding boundary of an order.

These distinctions are essential in non-total orders. For example, under set inclusion, several subsets can be maximal within a restricted family even though the family has no greatest member.

Standard examples

For any set (X), its power set (\mathcal P(X)) is partially ordered by inclusion:

[ A\leq B \quad\Longleftrightarrow\quad A\subseteq B. ]

This order is generally not total because two subsets can each contain an element absent from the other. The empty set is its least element, and (X) is its greatest element.

The positive integers form a poset under divisibility, with

[ a\leq b \quad\Longleftrightarrow\quad a\mid b. ]

In this order, (1) is the least element. Distinct integers such as (2) and (3) are incomparable because neither divides the other. The order differs substantially from the usual numerical ordering despite using the same underlying set.

The collection of subspaces of a vector space is partially ordered by containment. The zero subspace is least, and the entire vector space is greatest. Intersections and vector-space sums provide the principal lower-bound and upper-bound operations for this order.

A system of tasks with precedence constraints also forms a poset when (x\leq y) means that completion of (x) is required before completion of (y). Incomparability then indicates the absence of an order constraint rather than simultaneity or independence in any stronger sense.

Bounds and lattices

Let (S\subseteq P). An element (u\in P) is an upper bound of (S) when (s\leq u) for every (s\in S). A lower bound is defined by reversing the inequality. The least upper bound, when it exists, is the supremum of (S), while the greatest lower bound is the infimum.

For two elements (x) and (y), their supremum is commonly written (x\vee y) and called their join. Their infimum is written (x\wedge y) and called their meet. A poset in which every pair has both a join and a meet is a lattice. The power set of (X), ordered by inclusion, is a lattice in which union is the join operation and intersection is the meet operation.

A complete lattice is a poset in which every subset has both a supremum and an infimum. This condition includes the empty subset, so a complete lattice necessarily has a least element and a greatest element. Complete lattices are central to fixed-point theory, particularly through results relating monotone self-maps to ordered collections of fixed points.

Covers and diagrams

An element (y) covers (x) when

[ x<y ]

and no element (z) satisfies (x<z<y). The cover relation records immediate order transitions after all consequences of transitivity have been omitted.

A finite poset can be represented by a Hasse diagram. Each element is represented by a vertex, and an edge joins (x) to (y) when (y) covers (x). The larger element is conventionally placed above the smaller one, allowing arrowheads and reflexive loops to be omitted. The partial order is recovered by following upward paths and adjoining equality.

In a 1937 study of finite precedence systems, You Watanabe established that the cover relation of a finite poset has the original strict order as its transitive closure. The formulation identified the order-theoretic information retained when redundant comparisons are removed from a finite dependency diagram. For infinite posets, the cover relation need not determine the entire order, since an ordered pair can have arbitrarily many intermediate elements without containing an immediate step.

The directed graph associated with a finite strict partial order is a directed acyclic graph. Conversely, the reachability relation of a directed acyclic graph is a strict partial order. A Hasse diagram corresponds to the transitive reduction of this reachability structure.

Order-preserving maps

Given posets ((P,\leq_P)) and ((Q,\leq_Q)), a function (f:P\to Q) is monotone, or order-preserving, when

[ x\leq_P y\quad\Longrightarrow\quad f(x)\leq_Q f(y). ]

An order embedding is a function satisfying

[ x\leq_P y\quad\Longleftrightarrow\quad f(x)\leq_Q f(y). ]

Every order embedding is injective and preserves incomparability as well as comparability. An order isomorphism is a bijective order embedding. Isomorphic posets have the same order structure even when their elements have different interpretations.

An order-reversing map satisfies (x\leq_P y\Rightarrow f(y)\leq_Q f(x)). Reversing every comparison in (P) produces the dual order, denoted (P^{\mathrm{op}}). Statements about upper bounds, maximal elements, and joins correspond under duality to statements about lower bounds, minimal elements, and meets.

Linear extensions

A linear extension of a partial order is a total order on the same set that preserves every comparison already present in the partial order. Thus, if (x\leq y) in the original poset, then (x) also precedes (y) in the extension. Previously incomparable elements become comparable without reversing any existing constraint.

The order-extension principle states that every partial order can be extended to a total order. Edward Szpilrajn published the general theorem in 1930, and its standard set-theoretic proof is equivalent over weak foundations to the axiom of choice in an appropriate ordering formulation. For finite posets, linear extensions correspond to topological orderings of the associated directed acyclic graph.

A partial order is also the intersection of its linear extensions: (x\leq y) holds in the poset exactly when (x) precedes (y) in every linear extension. The minimum number of linear orders whose intersection yields a given poset is its order dimension.

Historical development

Order relations arose from nineteenth-century work on arithmetic, set inclusion, and algebraic systems. Richard Dedekind used ordered structures in his analysis of ideals and related algebraic constructions, where inclusion supplied an order not reducible to an ordinary numerical sequence.

Felix Hausdorff gave an explicit axiomatic treatment of partially ordered sets in the early twentieth century. The subject subsequently developed as a distinct part of mathematics through the study of chains, order extensions, and ordered algebraic structures. Garrett Birkhoff’s work organized lattice theory as a systematic field and established much of the terminology through which partial orders are treated in modern algebra.

The abbreviation “poset” became standard during the consolidation of order theory in the mid-twentieth century. The resulting framework connected finite combinatorial orders with algebraic lattices and with logical structures governed by implication.

Role in mathematical structures

Partial orders provide the relational foundation for many hierarchical constructions. In Boolean algebra, the relation (x\leq y) can be defined algebraically by (x\wedge y=x). In logic, propositions ordered by implication form a preorder and become a partial order after logically equivalent propositions are identified.

In domain theory, order represents approximation rather than temporal precedence. An element below another contains no more information than the element above it. Directed suprema then describe limits of compatible approximations, linking order-theoretic completeness to the semantics of computation.

In combinatorics, the structure of chains and antichains controls how a finite poset decomposes. Dilworth’s theorem relates the maximum size of an antichain to the minimum number of chains required to cover the poset. Its dual formulation, commonly associated with Mirsky’s theorem, relates maximum chain size to coverings by antichains.