Birkhoff's Representation Theorem - Birkhoff's Theorem

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 L is isomorphic to the lattice of lower sets of the partial order of the join-irreducible elements of L.

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

If one starts with a lower set S, lets x be the join of S, and constructs lower set T of the join-irreducible elements less than or equal to x, then S = T. For, every element of S clearly belongs to T, and any join-irreducible element less than or equal to x must (by join-primality) be less than or equal to one of the members of S, and therefore must (by the assumption that S is a lower set) belong to S itself. Conversely, if one starts with an element x of L, lets S be the join-irreducible elements less than or equal to x, and constructs y as the join of S, then x = y. For, as a join of elements less than or equal to x, y can be no greater than x itself, but if x is join-irreducible then x belongs to S while if x is the join of two or more join-irreducible items then they must again belong to S, so y ≥ x. Therefore, the correspondence is one-to-one and the theorem is proved.