40.02.01 · combinatorics / posets-lattices

Posets, Lattices, and Birkhoff's Representation Theorem

shipped3 tiersLean: none

Anchor (Master): Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e §3.4 (the fundamental theorem for finite distributive lattices) and Notes; Birkhoff 1937 *Duke Math. J.* 3 (rings of sets); Gratzer 2011 *Lattice Theory: Foundation* (Birkhauser) Ch. I-II for the structure theory of modular, distributive, and semimodular lattices

Intuition Beginner

Some collections of things come with a natural sense of "below" and "above" that is not a straight line. Whole numbers divide one another: $2$ sits below $6$ because $2$ divides $6$ , and $3$ also sits below $6$ , but $2$ and $3$ have no order between them — neither divides the other. Folders on a computer nest inside folders, tasks depend on earlier tasks, ancestors come before descendants. In each case you can compare some pairs and not others. A structure that records exactly which pairs are comparable, and nothing more, is a partial order.

Three rules capture the idea. Every item is below itself. If one item is below a second and the second is below a third, the first is below the third. And if two different items are each below the other, that cannot happen — being below is one-directional between distinct items. Anything obeying these three rules is a partially ordered set, or poset for short. The word "partial" is the whole point: unlike heights in a line-up, not every two items need to be ranked against each other.

To picture a poset you draw a Hasse diagram: put each item as a dot, place lower items lower on the page, and draw a line upward from each item only to the items that sit just above it with nothing in between. You never draw a line you could reach by climbing two shorter lines. Reading the picture, a straight upward path is a chain (everything on it is comparable), and a set of dots with no two joined by any path is an antichain (nothing on it is comparable).

Two questions organise the whole subject. Given any two items, is there a single best item sitting just below both of them, and a single best item sitting just above both? When both always exist, the poset is a lattice, and the two operations — greatest-lower and least-upper — behave like a careful version of "smaller of" and "larger of." Lattices are where order theory turns into algebra, and the cleanest lattices, the distributive ones, turn out to be exactly the lattices you can build by collecting sets and taking unions and intersections.

Visual Beginner

A Hasse diagram is the standard picture of a poset. Below is the diagram for the divisors of $12$ , ordered by "divides," and a separate small poset showing a chain and an antichain.

   divisors of 12 (a is below b iff a divides b)

            12
           /  \
          4    6
          |   / \
          2  /   3
           \/   /
            \  /
             1

   chain   1 - 2 - 4 - 12   (every pair comparable, length 4)
   antichain   { 4 , 6 }    (4 does not divide 6, 6 does not divide 4)

Read the left diagram from the bottom up. The element $1$ divides everything, so it sits at the bottom; $12$ is divisible by everything, so it sits at the top. A line goes up from $a$ to $b$ only when $b$ is a direct multiple with nothing strictly between — from $2$ up to $4$ and up to $6$ , but not directly from $2$ to $12$ , because $4$ and $6$ already lie between them.

This poset is in fact a lattice. For any two divisors the greatest common divisor is the single best item below both, and the least common multiple is the single best item above both. For $4$ and $6$ the item just below both is $g cd (4, 6) = 2$ and the item just above both is $lcm (4, 6) = 12$ .

pair	best below both (meet)	best above both (join)
$4$ and $6$	$2$	$12$
$2$ and $3$	$1$	$6$
$4$ and $3$	$1$	$12$

Worked example Beginner

Take the three-element set ${a, b, c}$ and collect all of its subsets, ordered by "is contained in." There are $8$ subsets, from the empty set at the bottom to the full set ${a, b, c}$ at the top. We work out its lattice structure by hand.

Step 1. List the subsets by size: size $0$ is $\emptyset$ ; size $1$ is ${a}, {b}, {c}$ ; size $2$ is ${a, b}, {a, c}, {b, c}$ ; size $3$ is ${a, b, c}$ . One set is below another when the first is contained in the second, so ${a} \subseteq {a, b}$ but ${a}$ and ${b}$ are not comparable.

Step 2. Find the best item below two given sets. For ${a, b}$ and ${a, c}$ , the sets contained in both are $\emptyset$ and ${a}$ , and the larger of these is ${a}$ . So the greatest-lower item — the meet — is their intersection ${a, b} \cap {a, c} = {a}$ .

Step 3. Find the best item above two given sets. For the same pair, the sets containing both are ${a, b, c}$ alone, so the least-upper item — the join — is their union ${a, b} \cup {a, c} = {a, b, c}$ .

Step 4. Count the chains and antichains. A longest chain climbs one element at a time: $\emptyset \subset {a} \subset {a, b} \subset {a, b, c}$ , length $4$ . A largest antichain is the three size- $2$ sets ${a, b}, {a, c}, {b, c}$ , no two comparable, size $3$ .

What this tells us: meet is intersection and join is union, so this subset poset is a lattice built entirely from sets. The longest chain has $4$ elements and the widest antichain has $3$ ; the next section's theorems tie such chain and antichain counts together for any poset.

Check your understanding Beginner

Formal definition Intermediate+

A partial order on a set $P$ is a binary relation $\leq$ that is reflexive ( $x \leq x$ ), antisymmetric ( $x \leq y$ and $y \leq x$ imply $x = y$ ), and transitive ( $x \leq y$ and $y \leq z$ imply $x \leq z$ ). The pair $(P, \leq)$ is a poset. Elements $x, y$ are comparable if $x \leq y$ or $y \leq x$ ; otherwise incomparable. We write $x < y$ for $x \leq y$ with $x \neq = y$ , and say $y$ covers $x$ , written $x ⋖ y$ , when $x < y$ and no $z$ satisfies $x < z < y$ . The Hasse diagram of a finite poset is the directed graph of the covering relation, drawn with $y$ above $x$ whenever $x ⋖ y$ .

A chain is a subset of pairwise comparable elements; an antichain is a subset of pairwise incomparable elements. The height of a finite poset is the size of its longest chain; the width is the size of its widest antichain. A linear extension of $P$ is a total order $\leq^{*}$ on the same underlying set with $x \leq y \Rightarrow x \leq^{*} y$ : a way to list the elements consistent with all comparabilities. The number of linear extensions, $e (P)$ , is the leading coefficient datum of the order polynomial $Ω_{P} (m)$ counting order-preserving maps $P \to [m]$ ^{[Stanley §3.3]}.

A down-set (or order ideal) of $P$ is a subset $I \subseteq P$ closed downward: $y \in I$ and $x \leq y$ imply $x \in I$ . Down-sets ordered by inclusion form the poset $J (P)$ . An element $x$ is join-irreducible if it covers exactly one element (equivalently, $x \neq = \hat{0}$ and $x = a \lor b$ forces $x = a$ or $x = b$ ); write $Irr (P)$ for the induced subposet of join-irreducibles.

A lattice is a poset in which every pair $x, y$ has a meet $x \land y$ (greatest lower bound) and a join $x \lor y$ (least upper bound). A lattice is bounded if it has a least element $\hat{0}$ and greatest element $\hat{1}$ ; complete if every subset (not just every pair) has a meet and a join — every finite lattice is complete. A lattice is distributive if $x \land (y \lor z) = (x \land y) \lor (x \land z)$ for all $x, y, z$ (equivalently the dual identity holds), and modular if $x \leq z$ implies $x \lor (y \land z) = (x \lor y) \land z$ . An element $y$ is a complement of $x$ in a bounded lattice if $x \land y = \hat{0}$ and $x \lor y = \hat{1}$ ; a distributive lattice in which every element is complemented is a Boolean lattice, the canonical example being the subset lattice $B_{n}$ of an $n$ -set.

Counterexamples to common slips Intermediate+

"Antisymmetry says no two elements are comparable both ways, so a poset has no cycles to worry about — like a total order." Antisymmetry forbids only $x \leq y \leq x$ with $x \neq = y$ ; it does not force comparability. The divisor poset of $12$ has incomparable $4$ and $6$ yet is a perfectly good poset. A total order is the special case where every pair is comparable.
"Every lattice is distributive." The diamond $M_{3}$ (a bottom, a top, and three pairwise-incomparable middle elements) is a lattice but fails distributivity: for the three atoms $a, b, c$ one has $a \land (b \lor c) = a \land \hat{1} = a$ while $(a \land b) \lor (a \land c) = \hat{0} \lor \hat{0} = \hat{0}$ . Distributivity is a genuine restriction.
"Distributive implies modular is the only relation, and modular implies distributive too." Modularity is strictly weaker. The pentagon $N_{5}$ is non-modular (hence non-distributive), but $M_{3}$ is modular yet non-distributive. The exact separations are the $M_{3} / N_{5}$ forbidden-sublattice theorems below.
"Join-irreducible just means an atom." An atom (an element covering $\hat{0}$ ) is join-irreducible, but in a chain of length $3$ , $0 ⋖ 1 ⋖ 2 ⋖ 3$ , every nonzero element is join-irreducible while only $1$ is an atom. Join-irreducibility is "covers exactly one element," which atoms satisfy but do not exhaust.

Key theorem with proof Intermediate+

The signature theorem is Birkhoff's representation theorem, because it pins down the finite distributive lattices completely: each one is the down-set lattice of a uniquely determined poset, and that poset is read off as the join-irreducibles. This converts a question about an algebraic structure (a lattice) into a question about a smaller combinatorial one (a poset).

Theorem (Birkhoff's representation theorem). Let $L$ be a finite distributive lattice and let $P = Irr (L)$ be the subposet of its join-irreducible elements. Then the map $$ \varphi : L \to J(P), \qquad \varphi(x) = {, p \in P : p \le x ,} $$ is an isomorphism of lattices. Conversely, for any finite poset $P$ the lattice $J (P)$ is distributive with join-irreducibles the principal down-sets, so $Irr (J (P)) ≅ P$ . The assignments $L \mapsto Irr (L)$ and $P \mapsto J (P)$ are mutually inverse.

Proof. First, $φ (x)$ is a down-set of $P$ : if $p \leq x$ and $q \leq p$ with $q$ join-irreducible, then $q \leq x$ by transitivity, so $q \in φ (x)$ . We show $φ$ is a bijection that preserves meet and join.

Order-preserving and injective. If $x \leq y$ then any $p \leq x$ has $p \leq y$ , so $φ (x) \subseteq φ (y)$ . For injectivity it suffices to show $x = ⋁ φ (x)$ , the join of the join-irreducibles below $x$ , for then $φ (x) = φ (y)$ forces $x = y$ . In a finite lattice every element is a join of join-irreducibles: argue by induction on the number of elements below $x$ . If $x$ is itself join-irreducible or $\hat{0}$ , the claim is immediate. Otherwise $x = a \lor b$ with $a, b < x$ , and each of $a, b$ is a join of join-irreducibles below it (induction), all of which are $\leq x$ ; their total join is $\geq a \lor b = x$ and $\leq x$ , hence equals $x$ . So $x = ⋁ φ (x)$ , and $φ$ is injective.

Surjective. Let $I \in J (P)$ be any down-set and set $x = ⋁ I$ (join over the finite set $I$ , with $⋁ \emptyset = \hat{0}$ ). Then $I \subseteq φ (x)$ since each $p \in I$ satisfies $p \leq x$ . For the reverse inclusion take $p \in φ (x)$ , so $p$ is join-irreducible and $p \leq x = ⋁_{q \in I} q$ . Here distributivity enters: in a finite distributive lattice a join-irreducible $p \leq ⋁_{q \in I} q$ satisfies $p \leq q$ for some $q \in I$ . Granting this, $p \leq q$ with $q \in I$ and $I$ a down-set give $p \in I$ . Hence $φ (x) \subseteq I$ , so $φ (x) = I$ and $φ$ is onto.

The join-prime lemma. It remains to prove that in a finite distributive lattice, join-irreducible implies join-prime: $p \leq a \lor b$ implies $p \leq a$ or $p \leq b$ (the case of a join over $I$ follows by iterating). Suppose $p \leq a \lor b$ . By distributivity, $p = p \land (a \lor b) = (p \land a) \lor (p \land b)$ . Since $p$ is join-irreducible, $p = p \land a$ or $p = p \land b$ , i.e. $p \leq a$ or $p \leq b$ .

Meet and join preserved. Because $φ$ is an order-isomorphism onto $J (P)$ (a bijection with $φ$ and $φ^{- 1}$ both order-preserving — the latter as $φ^{- 1} (I) = ⋁ I$ is monotone), it carries the meet and join of $L$ to those of $J (P)$ , which are intersection and union of down-sets. The converse direction is checked directly: $J (P)$ is a sublattice of the Boolean lattice $2^{P}$ under $\cap, \cup$ , hence distributive, and its join-irreducibles are exactly the principal down-sets $⟨ p ⟩ = {q : q \leq p}$ , which form a copy of $P$ . $□$

Bridge. This theorem is the foundational reason the chapter splits into "any poset" and "the distributive lattices it generates": $J (-)$ and $Irr (-)$ are mutually inverse, so distributive-lattice questions and finite-poset questions are the same question in two languages, and this is exactly the finite shadow of a duality that builds toward Stone and Priestley duality for the infinite case. The join-prime lemma is the central insight — distributivity is precisely what makes join-irreducibles behave like primes — and it generalises the inclusion-exclusion sign $(- 1)^{∣ T ∣}$ on the Boolean lattice that appeared in 40.01.01: the Boolean lattice $B_{n} = J (antichain of n)$ is the special case where $P$ has no relations, and Mobius inversion on a general $J (P)$ is dual to summation over down-sets. Putting these together, the representation theorem appears again in the matroid theory previewed below, where the lattice of flats records exactly which subsets are "down-closed" under the closure operator.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Prove that the diamond $M_{3}$ — elements $\hat{0} < a, b, c < \hat{1}$ with $a, b, c$ pairwise incomparable — is a modular lattice but not distributive.

Hint

For distributivity test $a \land (b \lor c)$ against $(a \land b) \lor (a \land c)$ . For modularity, check the modular law on all triples with $x \leq z$ ; the only comparabilities present are $\hat{0} \leq$ everything and everything $\leq \hat{1}$ .

Answer

Each pair of distinct atoms has meet $\hat{0}$ and join $\hat{1}$ , so $M_{3}$ is a lattice. Distributivity fails: $a \land (b \lor c) = a \land \hat{1} = a$ , but $(a \land b) \lor (a \land c) = \hat{0} \lor \hat{0} = \hat{0} \neq = a$ . For modularity, the law $x \lor (y \land z) = (x \lor y) \land z$ is required only when $x \leq z$ . The comparable pairs are exactly $\hat{0} \leq u$ and $u \leq \hat{1}$ for every $u$ . If $x = \hat{0}$ : $\hat{0} \lor (y \land z) = y \land z$ and $(\hat{0} \lor y) \land z = y \land z$ , agreeing. If $z = \hat{1}$ : $x \lor (y \land \hat{1}) = x \lor y$ and $(x \lor y) \land \hat{1} = x \lor y$ , agreeing. If $x = z$ : both sides equal $z$ . These exhaust the cases $x \leq z$ , so $M_{3}$ is modular. Rubric: full credit for the explicit distributivity failure and the case check confirming modularity on all $x \leq z$ .

Exercise 7 (hard, symbolic).

Prove the easy (" $\geq$ ") direction of Dilworth's theorem and the elementary lower-bound pairing: in any finite poset, the minimum number of chains covering $P$ is at least the maximum antichain size, and the minimum number of antichains covering $P$ equals the height (Mirsky's theorem). Prove Mirsky's theorem in full.

Hint

For the bound, no chain can contain two elements of an antichain. For Mirsky, rank each element by the length of the longest chain ending at it; show same-rank elements form antichains and that this uses exactly $h$ antichains where $h$ is the height.

Answer

A chain meets any antichain in at most one element (two elements of a chain are comparable, two of an antichain are not). So if $A$ is an antichain of size $w$ and the chains $C_{1}, \dots, C_{m}$ cover $P$ , each $C_{i}$ absorbs at most one element of $A$ , forcing $m \geq ∣ A ∣ = w$ ; thus minimum chain cover $\geq$ maximum antichain. For Mirsky, define the rank $r (x)$ to be the number of elements in a longest chain with top $x$ (so $r (x) \geq 1$ , and $r$ ranges over $1, \dots, h$ where $h$ is the height). If $x < y$ then appending $y$ to a longest chain ending at $x$ shows $r (y) > r (x)$ , so any two distinct elements with the same rank are incomparable: each level $A_{j} = {x : r (x) = j}$ is an antichain. These $h$ antichains partition $P$ , so the minimum antichain cover is $\leq h$ . Conversely a chain of length $h$ needs $h$ distinct antichains to cover it (one per element), so the minimum is $\geq h$ , giving equality. Rubric: full credit for the chain-meets-antichain bound and the rank-function antichain partition with both inequalities for Mirsky.

Exercise 8 (hard, symbolic).

Prove that for a finite poset $P$ , the lattice $J (P)$ of down-sets is graded (ranked) with rank function $rank (I) = ∣ I ∣$ , and deduce that the maximal chains of $J (P)$ are in bijection with the linear extensions of $P$ , so the number of maximal chains of $J (P)$ equals $e (P)$ .

Hint

A cover $I ⋖ I^{'}$ in $J (P)$ adds exactly one element. A maximal chain $\emptyset = I_{0} ⋖ I_{1} ⋖ \dots ⋖ I_{n} = P$ adds elements one at a time; read off the order in which elements are added.

Answer

Suppose $I ⊊ I^{'}$ are down-sets. Pick a minimal element $m$ of $I^{'} ∖ I$ (minimal in $P$ among that difference); then $I \cup {m}$ is a down-set (everything below $m$ lies in $I^{'}$ and, by minimality of $m$ in the difference, already in $I$ ) and satisfies $I ⊊ I \cup {m} \subseteq I^{'}$ . Hence a cover $I ⋖ I^{'}$ must have $∣ I^{'} ∣ = ∣ I ∣ + 1$ , so $∣ \cdot ∣$ strictly increases by one across each cover and is a rank function; $J (P)$ is graded of rank $∣ P ∣$ . A maximal chain $\emptyset = I_{0} ⋖ I_{1} ⋖ \dots ⋖ I_{n} = P$ adds one element $x_{k} = I_{k} ∖ I_{k - 1}$ at each step. Because each $I_{k}$ is a down-set, whenever $x_{i} < x_{j}$ in $P$ the smaller element must already be present when the larger is added, so $i < j$ : the sequence $x_{1}, \dots, x_{n}$ is a linear extension of $P$ . Conversely each linear extension determines such a chain by taking initial segments (each an order ideal). This is a bijection, so the maximal chains of $J (P)$ number $e (P)$ . Rubric: full credit for the single-element cover via a minimal element of the difference, the grading, and the linear-extension bijection in both directions.

Advanced results Master

The representation theorem makes the finite distributive lattices a tame class; the surrounding structure theory locates them inside the wider landscape of modular, semimodular, and geometric lattices, and connects the order-ideal construction to duality and to matroids.

Theorem 1 (Dilworth). In a finite poset $P$ , the minimum number of chains needed to cover $P$ equals the maximum size of an antichain ^{[Dilworth 1950]}. Dually (Mirsky), the minimum number of antichains covering $P$ equals the maximum chain length. Dilworth's theorem is equivalent to König's theorem on bipartite matchings: build a bipartite graph on two copies $P^{'}, P^{''}$ of the ground set with an edge $x^{'} y^{''}$ whenever $x < y$ ; a chain cover into $c$ chains corresponds to a matching of size $∣ P ∣ - c$ , and a maximum antichain corresponds to a minimum vertex cover, so the chain–antichain min–max is König's matching–cover min–max in disguise. The matching proof and its Hall-theorem packaging are developed in 40.04.02.

Theorem 2 ( $M_{3}$ – $N_{5}$ characterizations). A lattice $L$ is modular if and only if it has no sublattice isomorphic to the pentagon $N_{5}$ ; $L$ is distributive if and only if it has no sublattice isomorphic to $N_{5}$ or to the diamond $M_{3}$ ^{[Davey-Priestley Ch. 6]}. Thus the two adjacent classes are separated by exactly one extra forbidden sublattice: removing $N_{5}$ gives modularity, removing $N_{5}$ and $M_{3}$ gives distributivity. The proof in each direction is constructive — a failure of the modular or distributive law produces an explicit copy of the offending five-element lattice generated by the witnessing elements.

Theorem 3 (graded distributive lattices and the chain product). A finite distributive lattice $L ≅ J (P)$ is graded with rank $∣ P ∣$ , and its rank-generating function is the order polynomial of $P$ evaluated as a $q$ -series: $\sum_{I \in J (P)} q^{∣ I ∣}$ . When $P$ is an antichain of $n$ elements, $J (P) = B_{n}$ is the Boolean lattice with rank-generating function $(1 + q)^{n}$ , recovering the binomial coefficients; when $P$ is a disjoint union of chains of sizes $a_{1}, \dots, a_{k}$ , $J (P)$ is the product of chains $\prod [a_{i} + 1]$ , whose rank function is the Gaussian-binomial-style product. The Boolean lattice $B_{n} = \prod_{i = 1}^{n} [2]$ is the universal case, and every finite distributive lattice embeds in some $B_{n}$ as a sublattice (the embedding $φ$ into $2^{P}$ ).

Theorem 4 (complementation and Boolean lattices). A finite distributive lattice is complemented (every element has a complement) if and only if it is a Boolean lattice $B_{n}$ , equivalently if and only if its underlying poset of join-irreducibles is an antichain. In a distributive lattice complements are unique when they exist, and the complementation map $x \mapsto x^{'}$ is an order-reversing involution making $B_{n}$ a Boolean algebra; this is the finite, atomistic case of Stone's representation, where general Boolean algebras correspond to clopen sets of a totally disconnected compact space.

Theorem 5 (geometric lattices and matroids). A finite lattice is geometric (semimodular, with $\hat{1}$ a join of atoms) if and only if it is the lattice of flats of a matroid. Semimodularity — the condition that whenever $x$ and $y$ both cover $x \land y$ , then $x \lor y$ covers both — replaces distributivity, and the resulting lattices carry a well-defined rank function satisfying the submodular inequality $r (x \lor y) + r (x \land y) \leq r (x) + r (y)$ . Geometric lattices are generally non-distributive (the partition lattice $Π_{n}$ and the subspace lattice of $F_{q}^{n}$ are geometric but contain $M_{3}$ ), placing matroid theory on the modular/semimodular side of the order-theoretic map rather than the distributive side; the full matroid development is previewed for the matroid units of this section.

Synthesis. The fundamental theorem is the foundational reason finite order theory bifurcates cleanly: the functor $J (-)$ and its inverse $Irr (-)$ identify finite distributive lattices with finite posets, and this is exactly the duality that builds toward Stone and Priestley duality, with the Boolean lattices $B_{n} = J (antichain)$ as the complemented extreme where the duality becomes the finite case of Stone's theorem. The central insight running through every result is that distributivity equals join-primeness of join-irreducibles, which is dual to the inclusion-exclusion sign on the Boolean lattice from 40.01.01; once distributivity is dropped, the join-prime lemma fails, $M_{3}$ and $N_{5}$ appear as the minimal obstructions, and the theory continues along the modular and semimodular branch, where geometric lattices generalise the picture into matroids. Putting these together, Dilworth's theorem sits transversally: it is a min–max about any poset, dual to König's bipartite matching in 40.04.02, and it controls the width of $P$ which by the graded-lattice theorem governs the shape of $J (P)$ . The single object — a finite poset — thus simultaneously produces a distributive lattice by down-sets, a chain/antichain decomposition by Dilworth, and a Mobius-inversion calculus by the incidence algebra developed next in 40.02.02, so the representation theorem, the min–max duality, and the inversion calculus are three faces of the order relation rather than separate theories.

Full proof set Master

Proposition 1 (uniqueness in Birkhoff's theorem). If $L$ is a finite distributive lattice and $P, Q$ are finite posets with $L ≅ J (P) ≅ J (Q)$ , then $P ≅ Q$ .

Proof. The join-irreducibles of $J (P)$ are exactly the principal down-sets $⟨ p ⟩ = {q \in P : q \leq p}$ : such a down-set covers the single down-set $⟨ p ⟩ ∖ {p}$ , and conversely a down-set $I$ with more than one maximal element $p_{1} \neq = p_{2}$ splits as $I = (I ∖ {p_{1}}) \cup (I ∖ {p_{2}})$ , a join of two strictly smaller down-sets, hence is not join-irreducible. The map $p \mapsto ⟨ p ⟩$ is an order-isomorphism $P \to Irr (J (P))$ , since $p \leq p^{'}$ iff $⟨ p ⟩ \subseteq ⟨ p^{'} ⟩$ . Therefore $Irr (L)$ is determined by $L$ up to isomorphism, and $P ≅ Irr (J (P)) ≅ Irr (L) ≅ Irr (J (Q)) ≅ Q$ . $□$

Proposition 2 (Dilworth's theorem, full). In a finite poset $P$ , $min (chains covering P) = max (antichain size)$ .

Proof. The inequality $min (chain cover) \geq max (antichain)$ holds because a chain meets an antichain at most once. For the reverse, induct on $∣ P ∣$ ; the empty poset is immediate. Let $w$ be the maximum antichain size. Choose a maximal element $a$ and a minimal element $b \leq a$ in a maximal chain, and consider $P^{'} = P ∖ {a, b}$ (when this is a chain through one element, handle directly). If every maximum antichain of $P$ lies entirely in $P^{'}$ , then $P^{'}$ has the same width $w$ , and by induction it covers into $w$ chains; adding the chain ${b, a}$ (or extending an existing chain) covers $P$ with $w$ chains. Otherwise take a maximum antichain $A = {a_{1}, \dots, a_{w}}$ meeting both the strict down-set $D = {x : x \leq a_{i} some i}$ and the strict up-set $U = {x : x \geq a_{i} some i}$ in positive size. Then $D$ and $U$ each have $A$ as a maximum antichain and each is strictly smaller than $P$ in the relevant direction; by induction each decomposes into $w$ chains, with the chain through $a_{i}$ in $D$ glued to the chain through $a_{i}$ in $U$ at $a_{i}$ , yielding $w$ chains covering $D \cup U = P$ . Either way $P$ is covered by $w$ chains, so $min (chain cover) \leq w$ , giving equality. $□$

Proposition 3 ( $N_{5}$ obstructs modularity). A finite lattice $L$ is modular if and only if it contains no sublattice isomorphic to $N_{5}$ .

Proof. If $L$ has an $N_{5}$ sublattice $\hat{0} < a < c < \hat{1}$ , $\hat{0} < b < \hat{1}$ (relative bounds), the modular law fails on $a \leq c$ as in Exercise 5, so $L$ is non-modular. Conversely suppose $L$ is non-modular: there exist $x \leq z$ with $x \lor (y \land z) < (x \lor y) \land z$ (the inequality $\leq$ always holds). Set $a = x \lor (y \land z)$ , $c = (x \lor y) \land z$ , so $a < c$ . One checks $a \lor y = c \lor y = x \lor y$ and $a \land y = c \land y = y \land z$ using $x \leq z$ and absorption. Then ${a \land y, a, c, y, a \lor y}$ — bottom $a \land y = y \land z$ , top $a \lor y = x \lor y$ , the chain $a < c$ , and the side element $y$ — is a sublattice isomorphic to $N_{5}$ : $y$ is incomparable to both $a$ and $c$ (else $a = c$ would follow), and the meets and joins close up as computed. $□$

Proposition 4 (distributive $\Leftrightarrow$ no $M_{3}$ , no $N_{5}$ ). A finite lattice $L$ is distributive if and only if it contains no sublattice isomorphic to $M_{3}$ or $N_{5}$ .

Proof. A distributive lattice is modular, so excludes $N_{5}$ by Proposition 3, and excludes $M_{3}$ because distributivity fails in $M_{3}$ (Exercise 4) and passes to sublattices. Conversely assume $L$ excludes both. By Proposition 3, $L$ is modular. In a modular lattice that is non-distributive there exist elements whose distributivity defect generates a diamond: take $x, y, z$ with $(x \land y) \lor (x \land z) < x \land (y \lor z)$ and form the "median" elements $u = (x \land y) \lor (y \land z) \lor (z \land x)$ and $v = (x \lor y) \land (y \lor z) \land (z \lor x)$ ; modularity forces $u \leq v$ , and the three elements $(x \land v) \lor u$ , $(y \land v) \lor u$ , $(z \land v) \lor u$ are pairwise-incomparable atoms over $u$ with join $v$ , a sublattice isomorphic to $M_{3}$ . This contradicts the exclusion of $M_{3}$ , so $L$ is distributive. $□$

Proposition 5 ( $J (P)$ is distributive and recovers $P$ ). For any finite poset $P$ , $J (P)$ is a distributive lattice and $Irr (J (P)) ≅ P$ .

Proof. The down-sets of $P$ are closed under intersection and union: if $I, K$ are down-closed, so are $I \cap K$ and $I \cup K$ (a lower element of a member stays in the relevant set). Hence $J (P)$ is a sublattice of the power-set lattice $2^{P}$ under $\cap, \cup$ , with meet $\cap$ and join $\cup$ . Distributivity is inherited from $2^{P}$ , where $\cap$ distributes over $\cup$ setwise. By Proposition 1 the join-irreducibles of $J (P)$ are the principal down-sets $⟨ p ⟩$ , and $p \mapsto ⟨ p ⟩$ is an order-isomorphism $P \to Irr (J (P))$ . $□$

Connections Master

The incidence algebra of a finite poset and its Mobius function — the inverse of the zeta function, computed by Mobius inversion over down-sets — is the calculus built directly on the order relation defined here; it is developed in 40.02.02, which takes the Boolean-lattice inclusion-exclusion of 40.01.01 and generalises it to inversion on an arbitrary $J (P)$ . This unit owns the poset and lattice scaffolding; that unit owns the inversion theory on top of it, with the foundational reason being that the Mobius function lives in the incidence algebra of the very poset whose down-set lattice this theorem characterises.
Dilworth's chain–antichain min–max is the order-theoretic face of König's theorem on maximum matchings and minimum vertex covers in bipartite graphs, and of Hall's marriage theorem; the matching-theoretic proof, the LP-duality reading, and the deficiency version are developed in 40.04.02. The bridge is the bipartite graph on two copies of the ground set whose edges encode the strict order, under which a minimum chain cover is a maximum matching's complement and a maximum antichain is a minimum vertex cover.
The Boolean lattice $B_{n}$ , identified here as $J (antichain of n)$ and as the divisor lattice of a squarefree integer, is the indexing structure for inclusion-exclusion and for the elementary symmetric functions; its width is governed by Sperner's theorem and its chain decompositions by the symmetric chain decomposition, the extremal set theory continuing in 40.01.01's successors. Every finite distributive lattice embeds in some $B_{n}$ via the representation map $φ$ , making the Boolean lattice the universal ambient object for the whole distributive class.

Historical & philosophical context Master

Partial orders were isolated as an abstract structure by Hausdorff and by the early lattice theorists, but the decisive synthesis is Garrett Birkhoff's. In Rings of sets (1937) ^{[Birkhoff 1937]} he proved that every finite distributive lattice is a ring of sets — isomorphic to the lattice of down-sets of a poset — and recovered the poset as the join-irreducible elements, giving the representation theorem that bears his name. The result was the finite, combinatorial counterpart of Marshall Stone's 1936 representation of Boolean algebras as fields of clopen sets, and the two together established that lattice theory and topology/order were two readings of one structure.

The min–max law for chains and antichains was proved by Robert P. Dilworth in A decomposition theorem for partially ordered sets (1950) ^{[Dilworth 1950]}; its dual was made explicit by Leon Mirsky in 1971. The forbidden-sublattice characterizations of modular and distributive lattices via $N_{5}$ and $M_{3}$ are due to Dedekind (who introduced the modular law in his work on ideal lattices) and Birkhoff, and were placed in their modern dual-equivalence form by Hilary Priestley in the 1970s, extending Birkhoff's finite theorem to a duality between distributive lattices and ordered Stone spaces. The geometric-lattice viewpoint connecting semimodularity to matroids was developed by Birkhoff and Whitney in the 1930s, with the lattice of flats becoming the standard cryptomorphic presentation of a matroid in the hands of Rota and his school.

Bibliography Master

@article{birkhoff1937rings,
  author  = {Birkhoff, Garrett},
  title   = {Rings of sets},
  journal = {Duke Mathematical Journal},
  volume  = {3},
  number  = {3},
  year    = {1937},
  pages   = {443--454}
}

@article{dilworth1950decomposition,
  author  = {Dilworth, Robert P.},
  title   = {A decomposition theorem for partially ordered sets},
  journal = {Annals of Mathematics},
  volume  = {51},
  number  = {1},
  year    = {1950},
  pages   = {161--166}
}

@book{stanley2012ec1,
  author    = {Stanley, Richard P.},
  title     = {Enumerative Combinatorics, Volume 1},
  series    = {Cambridge Studies in Advanced Mathematics},
  volume    = {49},
  edition   = {2},
  publisher = {Cambridge University Press},
  year      = {2012}
}

@book{daveypriestley2002,
  author    = {Davey, B. A. and Priestley, H. A.},
  title     = {Introduction to Lattices and Order},
  edition   = {2},
  publisher = {Cambridge University Press},
  year      = {2002}
}

@book{gratzer2011lattice,
  author    = {Gr\"{a}tzer, George},
  title     = {Lattice Theory: Foundation},
  publisher = {Birkh\"{a}user},
  year      = {2011}
}

@book{trotter1992,
  author    = {Trotter, William T.},
  title     = {Combinatorics and Partially Ordered Sets: Dimension Theory},
  publisher = {Johns Hopkins University Press},
  year      = {1992}
}

@article{mirsky1971dual,
  author  = {Mirsky, Leon},
  title   = {A dual of Dilworth's decomposition theorem},
  journal = {American Mathematical Monthly},
  volume  = {78},
  number  = {8},
  year    = {1971},
  pages   = {876--877}
}

Prerequisites

40.01.01

Tier anchors

beginner: Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e (Cambridge) §3.1 (posets, Hasse diagrams, chains and antichains read by hand); Trotter 1992 *Combinatorics and Partially Ordered Sets* (Johns Hopkins) Ch. 1 for the pictorial intuition
intermediate: Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e §3.1-3.4 (covering relation, Dilworth and Mirsky, meet and join, lattices, distributive and modular lattices, M_3/N_5); Davey-Priestley 2002 *Introduction to Lattices and Order* 2e (Cambridge) Ch. 1-2, 5
master: Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e §3.4 (the fundamental theorem for finite distributive lattices) and Notes; Birkhoff 1937 *Duke Math. J.* 3 (rings of sets); Gratzer 2011 *Lattice Theory: Foundation* (Birkhauser) Ch. I-II for the structure theory of modular, distributive, and semimodular lattices

References

Stanley, R. P. — Enumerative Combinatorics, Volume 1 · Cambridge Studies in Advanced Mathematics 49, 2nd edition (2012). Chapter 3 develops partially ordered sets: §3.1 the basic definitions (cover relation, Hasse diagram, chain, antichain, order ideal/down-set, the order-ideal lattice J(P)); §3.2 the lattice of order ideals and the fundamental theorem for finite distributive lattices (Birkhoff's representation: L is isomorphic to J(P) where P is the induced subposet of join-irreducibles of L); §3.3 zeta polynomials and the order polynomial counting order-preserving maps and linear extensions; §3.4 distributive and modular lattices with the M_3/N_5 forbidden-sublattice characterizations. Dilworth's and Mirsky's theorems and the linear-extension count are stated and proved across §3.1-§3.5.
Birkhoff, G. — Rings of sets · *Duke Mathematical Journal* 3 (1937), 443-454. The original proof that every finite distributive lattice is isomorphic to a ring of sets, i.e. to the lattice of down-sets J(P) of a finite poset P, with P recovered as the poset of join-irreducible elements. This is the source of the representation theorem named for Birkhoff.
Davey, B. A. & Priestley, H. A. — Introduction to Lattices and Order · Cambridge University Press, 2nd edition (2002). Chapters 1-2 develop ordered sets, lattices as algebraic structures, complete lattices and the Knaster-Tarski fixed-point theorem; Chapter 5 gives the modern dual-equivalence form of Birkhoff's theorem (the finite case of Priestley duality) and the M_3/N_5 characterizations of distributive and modular lattices.
Dilworth, R. P. — A decomposition theorem for partially ordered sets · *Annals of Mathematics* 51 (1950), 161-166. The original proof that in any finite poset the minimum number of chains needed to cover the poset equals the maximum size of an antichain. The dual statement (minimum antichain cover = maximum chain) is Mirsky's theorem (1971).
Gratzer, G. — Lattice Theory: Foundation · Birkhauser (2011). Standard reference for the structure theory: modular and distributive lattices, the M_3/N_5 forbidden-sublattice theorems, semimodular and geometric lattices, complementation, and the connection between geometric lattices and matroids (every geometric lattice is the lattice of flats of a matroid).

Estimated time

beginner: 20m
intermediate: 50m
master: 90m