In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection. Indeed, these lattices of sets describe the scenery completely: every distributive lattice is—up to isomorphism—given as such a lattice of sets.
Free distributive lattices[edit]
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:
where are finite meets of elements of G. Moreover, since both meet and join are associative, commutative and idempotent, one can ignore duplicates and order, and represent a join of meets like the one above as a set of sets:
where the 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 is a subset of In this case the meet of will be below the meet of and hence one can safely remove the redundant set 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 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 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 the OEIS).
The numbers above count the number of elements in 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
- 0, 1, 4, 18, 166, 7579, 7828352, 2414682040996, 56130437228687557907786 (sequence A007153 in the OEIS).
See also[edit]
- Completely distributive lattice — a lattice in which infinite joins distribute over infinite meets
- Duality theory for distributive lattices
- Spectral space
No comments:
Post a Comment