Birkhoff's representation theorem

The partial order of join-irreducibles

In a lattice, an element ${\displaystyle x}$ is called join-irreducible if ${\displaystyle x}$ is not the join of a finite set of other elements. Equivalently, ${\displaystyle x}$ is join-irreducible if it is neither the bottom element of the lattice (the join of zero elements) nor the join of any two smaller elements. For instance, in the lattice of divisors of 120, there is no pair of elements whose join is 4, so 4 is join-irreducible. An element ${\displaystyle x}$ is join-prime if it differs from the bottom element, and whenever ${\displaystyle x\le y\vee z}$, either ${\displaystyle x\le y}$ or ${\displaystyle x\le z}$. In the same lattice, 4 is join-prime: whenever ${\displaystyle \mathrm{lcm}(y,z)}$ is divisible by 4, at least one of ${\displaystyle y}$ and ${\displaystyle z}$ must itself be divisible by 4.

In any lattice, a join-prime element must be join-irreducible. Equivalently, an element that is not join-irreducible is not join-prime. For, if an element ${\displaystyle x}$ is not join-irreducible, there exist smaller ${\displaystyle y}$ and ${\displaystyle z}$ such that ${\displaystyle x=y\vee z}$. But then ${\displaystyle x\le y\vee z}$, and ${\displaystyle x}$ is not less than or equal to either ${\displaystyle y}$ or ${\displaystyle z}$, showing that it is not join-prime.

There exist lattices in which the join-prime elements form a proper subset of the join-irreducible elements, but in a distributive lattice the two types of elements coincide. For, suppose that ${\displaystyle x}$ is join-irreducible, and that ${\displaystyle x\le y\vee z}$. This inequality is equivalent to the statement that ${\displaystyle x=x\wedge (y\vee z)}$, and by the distributive law ${\displaystyle x=(x\vee y)\wedge (x\vee z)}$. But since x is join-irreducible, at least one of the two terms in this join must be ${\displaystyle x}$ itself, showing that either ${\displaystyle x=(x\vee y)}$ (equivalently ${\displaystyle x\le y}$) or ${\displaystyle x=(x\vee z)}$ (equivalently ${\displaystyle x\le z}$).

The lattice ordering on the subset of join-irreducible elements forms a partial order; Birkhoff's theorem states that the lattice itself can be recovered from the lower sets of this partial order.

Birkhoff's theorem

In any partial order, the lower sets form a lattice in which the lattice's partial ordering is given by set inclusion, the join operation corresponds to set union, and the meet operation corresponds to set intersection, because unions and intersections preserve the property of being a lower set. Because set unions and intersections obey the distributive law, this is a distributive lattice. Birkhoff's theorem states that any finite distributive lattice can be constructed in this way.

Theorem. Any finite distributive lattice ${\displaystyle L}$ is isomorphic to the lattice of lower sets of the partial order of the join-irreducible elements of ${\displaystyle L}$.

That is, there is a one-to-one order-preserving correspondence between elements of ${\displaystyle L}$ and lower sets of the partial order. The lower set corresponding to an element ${\displaystyle x}$ of ${\displaystyle L}$ is simply the set of join-irreducible elements of ${\displaystyle L}$ that are less than or equal to ${\displaystyle x}$, and the element of ${\displaystyle L}$ corresponding to a lower set ${\displaystyle S}$ of join-irreducible elements is the join of ${\displaystyle S}$.

To prove the theorem, consider any lower set ${\displaystyle S}$ of join-irreducible elements, let ${\displaystyle x}$ be the join of ${\displaystyle S}$, and let ${\displaystyle T}$ be the lower set of the join-irreducible elements less than or equal to ${\displaystyle x}$. Then ${\displaystyle S=T}$. For, every element of ${\displaystyle S}$ clearly belongs to ${\displaystyle T}$, and any join-irreducible element less than or equal to ${\displaystyle x}$ must (by join-primality) be less than or equal to one of the members of ${\displaystyle S}$, and therefore must (by the assumption that ${\displaystyle S}$ is a lower set) belong to ${\displaystyle S}$ itself. Therefore, following the correspondence from lower sets to lattice elements and back preserves the identity of every lower set. In the other direction, it remains to show that following the correspondence from lattice elements to lower sets and back again preserves the identity of every lattice element. For an arbitrary element ${\displaystyle x}$ of ${\displaystyle L}$, let ${\displaystyle S}$ be the join-irreducible elements less than or equal to ${\displaystyle x}$, and let ${\displaystyle y}$ be the join of ${\displaystyle S}$. Then ${\displaystyle x=y}$. For, as a join of elements less than or equal to ${\displaystyle x}$, ${\displaystyle y}$ can be no greater than ${\displaystyle x}$ itself. But if ${\displaystyle x}$ is join-irreducible then ${\displaystyle x}$ belongs to ${\displaystyle S}$ while if ${\displaystyle x}$ is the join of two or more join-irreducible items then they must again belong to ${\displaystyle S}$. In either case, the presence of these elements in ${\displaystyle S}$ ensures that ${\displaystyle y\ge x}$. Therefore, the correspondence is one-to-one and the theorem is proved.

Rings of sets and preorders

In 1937, Garrett Birkhoff defined a ring of sets to be a family of sets that is closed under the operations of set unions and set intersections; later, motivated by applications in mathematical psychology, Doignon and Falmagne called the same structure a quasi-ordinal knowledge space. If the sets in a ring of sets are ordered by inclusion, they form a distributive lattice. The elements of the sets may be given a preorder in which ${\displaystyle x\le y}$ whenever some set in the ring contains ${\displaystyle x}$ but not ${\displaystyle y}$. The ring of sets itself is then the family of lower sets of this preorder, and any preorder gives rise to a ring of sets in this way.

Functoriality

Birkhoff's theorem, as stated above, is a correspondence between individual partial orders and distributive lattices. However, it can also be extended to a correspondence between order-preserving functions of partial orders and bounded homomorphisms of the corresponding distributive lattices. The direction of these maps is reversed in this correspondence.

Let ${\displaystyle \mathbf{2}}$ denote the partial order on the two-element set ${\displaystyle \{0,1\}}$ with the order relation ${\displaystyle 0\le 1}$, and (following Stanley) let ${\displaystyle J(P)}$ denote the distributive lattice of lower sets of a finite partial order ${\displaystyle P}$. Then the elements of ${\displaystyle J(P)}$ correspond one-for-one to the order-preserving functions from ${\displaystyle P}$ to ${\displaystyle \mathbf{2}}$. For, if ${\displaystyle f}$ is such a function, ${\displaystyle f^{-1}(0)}$ forms a lower set, and conversely if ${\displaystyle L}$ is a lower set one may define an order-preserving function ${\displaystyle f_L}$ that maps ${\displaystyle L}$ to ${\displaystyle 0}$ and that maps the remaining elements of ${\displaystyle P}$ to ${\displaystyle 1}$. If ${\displaystyle g}$ is any order-preserving function from ${\displaystyle Q}$ to ${\displaystyle P}$, one may define a function ${\displaystyle g^{\ast }}$ from ${\displaystyle J(P)}$ to ${\displaystyle J(Q)}$ that uses the composition of functions to map any element ${\displaystyle L}$ of ${\displaystyle J(P)}$ to ${\displaystyle f_L\circ g}$. This composite function maps ${\displaystyle Q}$ to ${\displaystyle \mathbf{2}}$ and therefore corresponds to an element ${\displaystyle g^{\ast }(L)=(f_L\circ g{)}^{-1}(0)}$ of ${\displaystyle J(Q)}$. Further, for any ${\displaystyle x}$ and ${\displaystyle y}$ in ${\displaystyle J(P)}$, ${\displaystyle g^{\ast }(x\wedge y)=g^{\ast }(x)\wedge g^{\ast }(y)}$ (an element of ${\displaystyle Q}$ is mapped by ${\displaystyle g}$ to the lower set ${\displaystyle x\cap y}$ if and only if it belongs both to the set of elements mapped to ${\displaystyle x}$ and the set of elements mapped to ${\displaystyle y}$) and symmetrically ${\displaystyle g^{\ast }(x\vee y)=g^{\ast }(x)\vee g^{\ast }(y)}$. Additionally, the bottom element of ${\displaystyle J(P)}$ (the function that maps all elements of ${\displaystyle P}$ to ${\displaystyle 0}$) is mapped by ${\displaystyle g^{\ast }}$ to the bottom element of ${\displaystyle J(Q)}$, and the top element of ${\displaystyle J(P)}$ is mapped by ${\displaystyle g^{\ast }}$ to the top element of ${\displaystyle J(Q)}$. That is, ${\displaystyle g^{\ast }}$ is a homomorphism of bounded lattices.

However, the elements of ${\displaystyle P}$ themselves correspond one-for-one with bounded lattice homomorphisms from ${\displaystyle J(P)}$ to ${\displaystyle \mathbf{2}}$. For, if ${\displaystyle x}$ is any element of ${\displaystyle P}$, one may define a bounded lattice homomorphism ${\displaystyle j_x}$ that maps all lower sets containing ${\displaystyle x}$ to ${\displaystyle 1}$ and all other lower sets to ${\displaystyle 0}$. And, for any lattice homomorphism from ${\displaystyle J(P)}$ to ${\displaystyle \mathbf{2}}$, the elements of ${\displaystyle J(P)}$ that are mapped to ${\displaystyle 1}$ must have a unique minimal element ${\displaystyle x}$ (the meet of all elements mapped to ${\displaystyle 1}$), which must be join-irreducible (it cannot be the join of any set of elements mapped to ${\displaystyle 0}$), so every lattice homomorphism has the form ${\displaystyle j_x}$ for some ${\displaystyle x}$. Again, from any bounded lattice homomorphism ${\displaystyle h}$ from ${\displaystyle J(P)}$ to ${\displaystyle J(Q)}$ one may use composition of functions to define an order-preserving map ${\displaystyle h^{\ast }}$ from ${\displaystyle Q}$ to ${\displaystyle P}$. It may be verified that ${\displaystyle g^{\ast \ast }=g}$ for any order-preserving map ${\displaystyle g}$ from ${\displaystyle Q}$ to ${\displaystyle P}$ and that ${\displaystyle h^{\ast \ast }=h}$ for any bounded lattice homomorphism ${\displaystyle h}$ from ${\displaystyle J(P)}$ to ${\displaystyle J(Q)}$.

In category theoretic terminology, ${\displaystyle J}$ is a contravariant hom-functor ${\displaystyle J=\mathrm{Hom}(-,\mathbf{2})}$ that defines a duality of categories between, on the one hand, the category of finite partial orders and order-preserving maps, and on the other hand the category of finite distributive lattices and bounded lattice homomorphisms.

Generalizations

Infinite distributive lattices

In an infinite distributive lattice, it may not be the case that the lower sets of the join-irreducible elements are in one-to-one correspondence with lattice elements. Indeed, there may be no join-irreducibles at all. This happens, for instance, in the lattice of all natural numbers, ordered with the reverse of the usual divisibility ordering (so ${\displaystyle x\le y}$ when ${\displaystyle y}$ divides ${\displaystyle x}$): any number ${\displaystyle x}$ can be expressed as the join of numbers ${\displaystyle xp}$ and ${\displaystyle xq}$ where ${\displaystyle p}$ and ${\displaystyle q}$ are distinct prime numbers. However, elements in infinite distributive lattices may still be represented as sets via Stone's representation theorem for distributive lattices, a form of Stone duality in which each lattice element corresponds to a compact open set in a certain topological space. This generalized representation theorem can be expressed as a category-theoretic duality between distributive lattices and spectral spaces (sometimes called coherent spaces, but not the same as the coherent spaces in linear logic), topological spaces in which the compact open sets are closed under intersection and form a base for the topology. Hilary Priestley showed that Stone's representation theorem could be interpreted as an extension of the idea of representing lattice elements by lower sets of a partial order, using Nachbin's idea of ordered topological spaces. Stone spaces with an additional partial order linked with the topology via Priestley separation axiom can also be used to represent bounded distributive lattices. Such spaces are known as Priestley spaces. Further, certain bitopological spaces, namely pairwise Stone spaces, generalize Stone's original approach by utilizing two topologies on a set to represent an abstract distributive lattice. Thus, Birkhoff's representation theorem extends to the case of infinite (bounded) distributive lattices in at least three different ways, summed up in duality theory for distributive lattices.

Median algebras and related graphs

Birkhoff's representation theorem may also be generalized to finite structures other than distributive lattices. In a distributive lattice, the self-dual median operation $${\displaystyle m(x,y,z)=(x\vee y)\wedge (x\vee z)\wedge (y\vee z)=(x\wedge y)\vee (x\wedge z)\vee (y\wedge z)}$$ gives rise to a median algebra, and the covering relation of the lattice forms a median graph. Finite median algebras and median graphs have a dual structure as the set of solutions of a 2-satisfiability instance; Barthélemy and Constantin formulate this structure equivalently as the family of initial stable sets in a mixed graph. For a distributive lattice, the corresponding mixed graph has no undirected edges, and the initial stable sets are just the lower sets of the transitive closure of the graph. Equivalently, for a distributive lattice, the implication graph of the 2-satisfiability instance can be partitioned into two connected components, one on the positive variables of the instance and the other on the negative variables; the transitive closure of the positive component is the underlying partial order of the distributive lattice.

Finite join-distributive lattices and antimatroids

Another result analogous to Birkhoff's representation theorem, but applying to a broader class of lattices, is the theorem of Edelman (1980) that any finite join-distributive lattice may be represented as an antimatroid, a family of sets closed under unions but in which closure under intersections has been replaced by the property that each nonempty set has a removable element.