Birkhoff's Representation Theorem - Functoriality

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 2 denote the partial order on the two-element set {0, 1}, with the order relation 0 < 1, and (following Stanley) let J(P) denote the distributive lattice of lower sets of a finite partial order P. Then the elements of J(P) correspond one-for-one to the order-preserving functions from P to 2. For, if ƒ is such a function, ƒ−1(0) forms a lower set, and conversely if L is a lower set one may define an order-preserving function ƒ_L that maps L to 0 and that maps the remaining elements of P to 1. If g is any order-preserving function from Q to P, one may define a function g* from J(P) to J(Q) that uses the composition of functions to map any element L of J(P) to ƒ_L ∘ g. This composite function maps Q to 2 and therefore corresponds to an element g*(L) = (ƒ_L ∘ g)−1(0) of J(Q). Further, for any x and y in J(P), g*(x ∧ y) = g*(x) ∧ g*(y) (an element of Q is mapped by g to the lower set x ∩ y if and only if belongs both to the set of elements mapped to x and the set of elements mapped to y) and symmetrically g*(x ∨ y) = g*(x) ∨ g*(y). Additionally, the bottom element of J(P) (the function that maps all elements of P to 0) is mapped by g* to the bottom element of J(Q), and the top element of J(P) is mapped by g* to the top element of J(Q). That is, g* is a homomorphism of bounded lattices.

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

In category theoretic terminology, J is a contravariant hom-functor J = Hom(—,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.