Distributive Lattice - Free Distributive Lattices

Free Distributive Lattices

The free distributive lattice over a set of generators G can be constructed much more easily than a general free lattice. The first observation is that, using the laws of distributivity, every term formed by the binary operations and on a set of generators can be transformed into the following equivalent normal form:

M₁ M₂ ... M_n

where the M_i are finite meets of elements of G. Moreover, since both meet and join are commutative and idempotent, one can ignore duplicates and order, and represent a join of meets like the one above as a set of sets:

{N₁, N₂, ..., N_n},

where the N_i are finite subsets of G. However, it is still possible that two such terms denote the same element of the distributive lattice. This occurs when there are indices j and k such that N_j is a subset of N_k. In this case the meet of N_k will be below the meet of N_j, and hence one can safely remove the redundant set N_k without changing the interpretation of the whole term. Consequently, a set of finite subsets of G will be called irredundant whenever all of its elements N_i are mutually incomparable (with respect to the subset ordering); that is, when it forms an antichain of finite sets.

Now the free distributive lattice over a set of generators G is defined on the set of all finite irredundant sets of finite subsets of G. The join of two finite irredundant sets is obtained from their union by removing all redundant sets. Likewise the meet of two sets S and T is the irredundant version of { NM | N in S, M in T}. The verification that this structure is a distributive lattice with the required universal property is routine.

The number of elements in free distributive lattices with n generators is given by the Dedekind numbers. These numbers grow rapidly, and are known only for n ≤ 8; they are

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (sequence A000372 in OEIS).

The numbers above count the number of free distributive lattices in which the lattice operations are joins and meets of finite sets of elements, including the empty set. If empty joins and empty meets are disallowed, the resulting free distributive lattices have two fewer elements; their numbers of elements form the sequence

1, 4, 18, 166, 7579, 7828352, 2414682040996, 56130437228687557907786 (sequence A007153 in OEIS).