Partial Orders

Partial orders are the quiet backbone of dependency management in software: a build system or package manager orders tasks or packages by "must happen before," and a valid schedule is precisely a linear extension of that partial order — a total order compatible with it, produced via topological sorting. In distributed computing, the "happens-before" relation on events across different processes (Lamport's causal order) is a partial order precisely because events on different machines that don't communicate are genuinely incomparable in time. In algebra and combinatorics, the divisor lattice, the subset lattice, and the poset of subgroups of a group under inclusion are all standard partial orders whose Hasse diagrams reveal structural symmetries. In logic and type theory, the subtyping relation and the specialization order on formulas are partial orders governing which terms can be safely substituted for others. In statistics and economics, partial orders model incomplete preferences and stochastic dominance, where one distribution is "at least as good" as another only for some but not all criteria. In cryptography and formal verification, security levels form a partial order (the classic example being multi-level security lattices), where information may flow upward but incomparable levels cannot be compared at all. Understanding Properties of Relations: Reflexive, Symmetric, Transitive is precisely the prerequisite that makes all of these applications precise, and pushing the comparability requirement to its limit leads directly to Total Orders and Chains and eventually Well-Orders and Minimal Elements.

Ask the tutor: How does the existence-of-maximal-element theorem for finite posets connect to Zorn's Lemma for infinite posets?

A partial order is best understood as a generalization of "smaller than or equal to" that allows elements to be simply unrelated rather than forcing every pair into a definite before/after relationship. The set of positive divisors of $12$, ordered by divisibility, is a natural first example: $1 \mid 2$, $2 \mid 4$, $2 \mid 6$, and so on, but $2$ and $3$ are incomparable — neither divides the other. Antisymmetry here is the fact that if $a \mid b$ and $b \mid a$ for positive integers, then $a = b$; reflexivity is $a \mid a$; transitivity is the familiar fact that a divisor of a divisor is a divisor. The Hasse diagram is the standard tool for visualizing a finite poset. Elements are drawn as points, placed so that if $a \prec b$ then $a$ is drawn strictly lower than $b$; an edge is drawn between $a$ and $b$ exactly when $b$ covers $a$. Crucially, edges for non-covering relations (like $1 \prec 4$, which is implied by $1\prec 2\prec 4$) are omitted, because transitivity lets us reconstruct them: $x \preceq y$ in the poset if and only if there is an upward path of edges from $x$ to $y$ in the diagram (or $x=y$). This is why a Hasse diagram, despite showing only a small subset of the pairs in $R$, faithfully encodes the entire partial order.

Notice in the figure that $3$ and $4$ are drawn at incomparable heights with no connecting path — indeed $3 \nmid 4$ and $4 \nmid 3$ — so they are genuinely incomparable in this poset, even though both lie "between" $1$ and $12$ in the sense that $1$ divides each and each divides $12$. This is the phenomenon that a total order can never exhibit, and it is exactly what makes posets strictly more expressive.

The corollary follows by applying the theorem to the dual poset $(A, \preceq^{\text{op}})$, where $a \preceq^{\text{op}} b$ iff $b \preceq a$; one checks immediately that $\preceq^{\text{op}}$ is again reflexive, antisymmetric, and transitive (the three axioms are each symmetric in the roles of "$a$ precedes $b$" once reversed consistently), so it is a partial order, and a maximal element of $(A,\preceq^{\text{op}})$ is precisely a minimal element of $(A,\preceq)$.

Example 1: Subset order on a power set, and a non-unique maximum. Let $A = \{1,2,3\}$ and let $P(A)$ be its power set, ordered by $\subseteq$. We verify $\subseteq$ is a partial order on $P(A)$ and then locate its maximal/minimal elements. Reflexivity: for any $X \subseteq A$, $X \subseteq X$ trivially (every element of $X$ is an element of $X$). Antisymmetry: if $X \subseteq Y$ and $Y \subseteq X$, then every element of $X$ is in $Y$ and vice versa, so $X$ and $Y$ have exactly the same elements, i.e. $X = Y$ by the axiom of extensionality. Transitivity: if $X \subseteq Y$ and $Y \subseteq Z$, then for any $x \in X$ we have $x \in Y$ (since $X \subseteq Y$) and hence $x \in Z$ (since $Y \subseteq Z$); thus $X \subseteq Z$. So $(P(A), \subseteq)$ is a poset. It has $2^3 = 8$ elements: $\varnothing, \{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}$. Now consider the sub-poset $B = P(A) \setminus \{\varnothing, \{1,2,3\}\}$, i.e. we remove the empty set and the full set, keeping only the six proper nonempty subsets, still ordered by $\subseteq$. This is a poset with $6$ elements (finite and nonempty), so by the Theorem it has a maximal element — but let's see there are three of them, not one. The elements $\{1,2\}, \{1,3\}, \{2,3\}$ are each maximal in $B$: none of the remaining elements of $B$ properly contains any of them (the only sets that would properly contain, say, $\{1,2\}$, are $\{1,2,3\}$, which has been removed). Yet none of $\{1,2\},\{1,3\},\{2,3\}$ is comparable to the others — $\{1,2\} \not\subseteq \{1,3\}$ and $\{1,3\}\not\subseteq\{1,2\}$, for instance, since $2 \in \{1,2\}\setminus\{1,3\}$ and $3\in\{1,3\}\setminus\{1,2\}$. So $B$ has three distinct maximal elements and no single greatest element (an element $g$ with $x \preceq g$ for all $x \in B$). This shows the Theorem's conclusion — existence of a maximal element — is the correct and sharp statement; uniqueness genuinely can fail. Symmetrically, $\{1\},\{2\},\{3\}$ are the three minimal elements of $B$.

Example 2: Divisibility on $\{1,\dots,30\}$, bounds and covers. Let $A = \{1, 2, \dots, 30\}$ with $a \preceq b$ meaning $a \mid b$ (i.e. $b$ is an integer multiple of $a$). This is a partial order: reflexivity holds since $a \mid a$ (take quotient $1$); antisymmetry holds because if $a \mid b$ and $b \mid a$ with $a, b$ positive integers, then $b = ka$ and $a = jb$ for positive integers $j,k$, so $a = jka$, forcing $jk = 1$, hence $j = k = 1$ and $a = b$; transitivity holds because if $b = ka$ and $c = mb$ then $c = mka$, so $a \mid c$. Consider the elements $18$ and $24$. Their common lower bounds in $A$ are the common divisors of $18$ and $24$ lying in $A$: divisors of $18$ are $1,2,3,6,9,18$; divisors of $24$ are $1,2,3,4,6,8,12,24$; the common divisors are $\{1,2,3,6\}$. Among these, $6$ divides every other common divisor ($1,2,3 \mid 6$), so $6$ is the greatest lower bound (infimum) of $\{18,24\}$ in $(A,\mid)$ — this recovers $\gcd(18,24)=6$. Their common upper bounds in $A$ are common multiples of $18$ and $24$ that lie in $\{1,\dots,30\}$. The least common multiple is $\operatorname{lcm}(18,24) = 72$, which already exceeds $30$; every common multiple of $18$ and $24$ is a multiple of $72$ and hence at least $72$. So $\{18, 24\}$ has no upper bound at all within $A$ — the ambient set $A$ is simply too small. This is an important cautionary feature of bounds in posets: existence of bounds is relative to the ambient set, and can fail even when both elements exist and $A$ is finite. Note also that $18$ covers no element of the form "one prime factor removed" uniformly — the elements covered by $18$ in this poset are exactly $9$ and $6$ (since $18/9 = 2$ and $18/6=3$ are prime, while $18/2 = 9$, $18/3=6$ are the largest proper divisors giving covering relations; one checks $9 \prec 18$ with nothing strictly between since any $d$ with $9 \mid d \mid 18$, $d\ne 9,18$ would need $d/9 \in\{1,2\}$ forcing $d=9$ or $d=18$), illustrating how covers are computed from the divisor structure rather than by simple arithmetic difference.