This is about lattice theory. For other similarly named results, see Birkhoff's theorem (disambiguation). In mathematics, Birkhoff's representation theorem for distributive lattices states that the elements of any finite distributive lattice can be represented as finite sets, in such a way that the lattice operations correspond to unions and intersections of sets. Here, a lattice is an abstract structure with two binary operations, the "meet" and "join" operations, which must obey certain axioms; it is distributive if these two operations obey the distributive law. The union and intersection operations, in a family of sets that is closed under these operations, automatically form a distributive lattice, and Birkhoff's representation theorem states that (up to isomorphism) every finite distributive lattice can be formed in this way. It is named after Garrett Birkhoff, who published a proof of it in 1937.
The theorem can be interpreted as providing a one-to-one correspondence between distributive lattices and partial orders, between quasi-ordinal knowledge spaces and preorders, or between finite topological spaces and preorders.
The name "Birkhoff's representation theorem" has also been applied to two other results of Birkhoff, one from 1935 on the representation of Boolean algebras as families of sets closed under union, intersection, and complement (so-called fields of sets, closely related to the rings of sets used by Birkhoff to represent distributive lattices), and Birkhoff's HSP theorem representing algebras as products of irreducible algebras. Birkhoff's representation theorem has also been called the fundamental theorem for finite distributive lattices.
Background and examples Many lattices can be defined in such a way that the elements of the lattice are represented by sets, the join operation of the lattice is represented by set union, and the meet operation of the lattice is represented by set intersection. For instance, the Boolean lattice defined from the family of all subsets of a finite set has this property. More generally any finite topological space has a lattice of sets as its family of open sets. Because set unions and intersections obey the distributive law, any lattice defined in this way is a distributive lattice. Birkhoff's theorem states that in fact all finite distributive lattices can be obtained this way, and later generalizations of Birkhoff's theorem state a similar thing for infinite distributive lattices.
As an example of a finite distributive lattice, consider the finite set of divisors of some composite number, such as (in the figure) 120, partially ordered by divisibility. Any two of these divisors have a unique greatest common factor, the largest number that divides both of them; for instance, the greatest common divisor of 12 and 20 is 4. They also have a unique least common multiple, which for 12 and 20 is 60.This example of a lattice of divisors can be found, for instance, at The greatest common factor and least common multiple both belong to the same finite set of divisors. If we denote the greatest common factor operation by the meet operator and the least common multiple operation by the join operator , then these two operations satisfy the distributive law, in either of two equivalent forms:
Because these two operators are the greatest lower bound and least upper bound operators in a partially ordered set, respectively, and obey the distributive law, the divisors with these operations form a finite distributive lattice.
The prime powers that divide 120 are 2, 3, 4, 5, and 8. One may associate each divisor of 120 with the set of prime powers that divide it: thus, 12 is associated with the set , while 20 is associated with the set . Under this association, every greatest common factor operation on two divisors corresponds to the set-theoretic intersection of two sets of prime powers. For instance, the fact that corresponds to the fact that . In the same way, every least common multiple operation on two divisors corresponds to the set-theoretic union of two sets of prime powers. For instance, the fact that corresponds to the fact that . The prime powers 2, 3, 4, 5, and 8 appearing as elements in these sets may themselves be partially ordered by divisibility; in this smaller partial order, 2 ≤ 4 ≤ 8 and there are no order relations between other pairs. The 16 sets of prime powers that are associated with divisors of 120 are the lower sets of this smaller partial order, subsets of elements such that if and belongs to the subset, then must also belong to the subset. From any lower set , one can recover the associated divisor by computing the least common multiple of the prime powers in . Thus, the partial order on the five prime powers 2, 3, 4, 5, and 8 carries enough information to recover the entire original 16-element divisibility lattice.
Birkhoff's theorem states that this relation between the operations and of the lattice of divisors and the operations and of the associated lower sets of prime powers is not coincidental, and not dependent on the specific properties of prime numbers and divisibility: the elements of any finite distributive lattice may be associated with lower sets of a partial order in the same way.
The power set of all subsets of a given -element set forms a field of sets, which form a Boolean algebra under intersections and unions. This is a special case of a finite distributive lattice, and corresponds under Birkhoff's representation theorem to a partially ordered set of the elements, each two of which are incomparable. An isomorphic distributive lattice to the power set can also be constructed as the lattice of divisors of a square-free integer with prime factors. As another example, the free distributive lattice on generators corresponds, under Birkhoff's theorem, to the family of lower sets of the power set of an -element set. Here, the power set is treated as a partial order with the subset predicate as its comparison operation, forgetting its lattice structure. The number of lower sets of the power set, and the number of elements of the free distributive lattice, are given by the Dedekind numbers, which grow doubly exponentially as a function
The partial order of join-irreducibles In a lattice, an element is called join-irreducible if is not the join of a finite set of other elements. Equivalently, 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 is join-prime if it differs from the bottom element, and whenever , either or . In the same lattice, 4 is join-prime: whenever is divisible by 4, at least one of and 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 is not join-irreducible, there exist smaller and such that . But then , and is not less than or equal to either or , 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 is join-irreducible, and that . This inequality is equivalent to the statement that , and by the distributive law . But since x is join-irreducible, at least one of the two terms in this join must be itself, showing that either (equivalently ) or (equivalently ).
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.
That is, there is a one-to-one order-preserving correspondence between elements of and lower sets of the partial order. The lower set corresponding to an element of is simply the set of join-irreducible elements of that are less than or equal to , and the element of corresponding to a lower set of join-irreducible elements is the join of .
To prove the theorem, consider any lower set of join-irreducible elements, let be the join of , and let be the lower set of the join-irreducible elements less than or equal to . Then . For, every element of clearly belongs to , and any join-irreducible element less than or equal to must (by join-primality) be less than or equal to one of the members of , and therefore must (by the assumption that is a lower set) belong to 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 of , let be the join-irreducible elements less than or equal to , and let be the join of . Then . For, as a join of elements less than or equal to , can be no greater than itself. But if is join-irreducible then belongs to while if is the join of two or more join-irreducible items then they must again belong to . In either case, the presence of these elements in ensures that . 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 whenever some set in the ring contains but not . 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.
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 denote the partial order on the two-element set with the order relation , and (following Stanley) let denote the distributive lattice of lower sets of a finite partial order . Then the elements of correspond one-for-one to the order-preserving functions from to . For, if is such a function, forms a lower set, and conversely if is a lower set one may define an order-preserving function that maps to and that maps the remaining elements of to . If is any order-preserving function from to , one may define a function from to that uses the composition of functions to map any element of to . This composite function maps to and therefore corresponds to an element of . Further, for any and in , (an element of is mapped by to the lower set if and only if it belongs both to the set of elements mapped to and the set of elements mapped to ) and symmetrically . Additionally, the bottom element of (the function that maps all elements of to ) is mapped by to the bottom element of , and the top element of is mapped by to the top element of . That is, is a homomorphism of bounded lattices.