Birkhoff's Representation Theorem - Generalizations

Generalizations

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 x ≤ y when y divides x): any number x can be expressed as the join of numbers xp and xq where p and 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 coherent spaces (sometimes called spectral spaces), 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 distributve 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.

Birkhoff's representation theorem may also be generalized to finite structures other than distributive lattices. In a distributive lattice, the self-dual median operation

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 & Constantin (1993) 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.

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.