Partial Order

A partial order is a binary relation on a set that describes an ordering without requiring every pair of elements to be comparable. It is reflexive, antisymmetric, and transitive. A set equipped with such a relation is called a partially ordered set, or poset. Unlike a numerical ranking, a partial order can represent branching hierarchies and constraints that leave some elements unrelated. (lara.epfl.ch)

Definition and related relations

Let $P$ be a set and let $\leq$ be a relation on $P$. The relation is a partial order if, for all $x,y,z\in P$, it satisfies three axioms:

• Reflexivity: $x\leq x$.
• Antisymmetry: if $x\leq y$ and $y\leq x$, then $x=y$.
• Transitivity: if $x\leq y$ and $y\leq z$, then $x\leq z$.

The notation $(P,\leq)$ records both the underlying set and its order. Antisymmetry does not prohibit comparisons in both directions when the elements are equal. (lara.epfl.ch)

Two elements are comparable when $x\leq y$ or $y\leq x$; otherwise they are incomparable. A total order, also called a linear order, is a partial order in which every pair is comparable. Thus “partial” permits incomparability but does not require it. The usual order on the real numbers is a total order. (math.mit.edu)

The associated strict order is defined by

It is irreflexive and transitive. Conversely, adjoining equality to an irreflexive, transitive relation produces a partial order. (lara.epfl.ch)

Examples and constructions

In set theory, inclusion orders the power set $\mathcal P(S)$: $A\leq B$ means $A\subseteq B$. For $S=\{a,b\}$, the subsets $\{a\}$ and $\{b\}$ are incomparable, although both lie above the empty set and below $S$. (lara.epfl.ch)

Divisibility orders the positive integers: $a\leq b$ means $a\mid b$. For example, $2$ and $3$ are incomparable, while both precede $6$. Restricting this relation to the divisors of $12$ gives a finite poset with elements $1,2,3,4,6,12$. (math.mit.edu)

The Cartesian product of two posets carries the product order:

For numerical coordinates, $(1,3)$ and $(2,2)$ are therefore incomparable. This order differs from lexicographic ordering, which compares the first differing coordinate. (math.mit.edu)

Reversing every comparison gives the dual order, defined by $x\leq_{\mathrm{op}}y$ exactly when $y\leq x$. Duality exchanges statements about upper and lower bounds, or greatest and least elements. (math.hawaii.edu)

Hasse diagrams, chains, and antichains

A finite poset is commonly represented by a Hasse diagram. An element $y$ covers $x$ if $x<y$ and no element $z$ satisfies $x<z<y$. The diagram places $y$ above $x$ and connects them when this covering condition holds. Reflexive comparisons and comparisons implied by transitivity are omitted. (math.mit.edu)

In a finite poset, $x<y$ precisely when an upward path connects $x$ to $y$. This description requires care for infinite orders: the usual order on the real numbers has no covering pairs, because another real number lies between any two distinct ones. (math.mit.edu)

A chain is a subset whose elements are pairwise comparable. An antichain is a subset whose distinct elements are pairwise incomparable. For a finite poset, its height is commonly measured by the largest number of elements in a chain, and its width by the largest number in an antichain. Some authors measure chain length by the number of steps instead. Dilworth’s theorem states that the width equals the minimum number of chains needed to partition the poset. (math.mit.edu)

Extremal elements and bounds

An element $m$ is minimal if no element is strictly below it; it is least if $m\leq x$ for every $x\in P$. Dually, an element is maximal if nothing lies strictly above it, and greatest if it lies above every element. Multiple minimal or maximal elements may exist, but a least or greatest element, when present, is unique. (lara.epfl.ch)

For a subset $A\subseteq P$, an upper bound is an element above every member of $A$. Its supremum is the least upper bound. The infimum is the greatest lower bound. Bounds need not belong to $A$, and even a bounded subset need not possess a supremum or infimum. (scss.tcd.ie)

A lattice is a poset in which every pair has a supremum, called its join, and an infimum, called its meet. A complete lattice has both for every subset, including the empty subset. Power sets ordered by inclusion are complete lattices: joins are unions and meets are intersections. With complementation, they also provide standard examples of Boolean algebras. (math.hawaii.edu)

Linear extensions and computation

A linear extension is a total order that preserves all comparisons in the original poset. Every finite poset has one, although incomparable elements can often be placed in either order, producing multiple extensions. (math.mit.edu)

In graph theory, a directed acyclic graph defines a partial order through reachability together with equality. Its transitive closure records indirect dependencies. A topological sorting algorithm constructs a linear extension by placing each vertex before its successors. This supports scheduling tasks subject to prerequisite constraints without imposing an order on independent tasks. Standard implementations run in $O(|V|+|E|)$ time for a graph with vertex set $V$ and edge set $E$. (cs.cornell.edu)