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:
- M1 M2 ... Mn
where the Mi 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:
- {N1, N2, ..., Nn},
where the Ni 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 Nj is a subset of Nk. In this case the meet of Nk will be below the meet of Nj, and hence one can safely remove the redundant set Nk 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 Ni 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).
Read more about this topic: Distributive Lattice
Famous quotes containing the word free:
“Have you ever been up in your plane at night, alone, somewhere, 20,000 feet above the ocean?... Did you ever hear music up there?... It’s the music a man’s spirit sings to his heart, when the earth’s far away and there isn’t any more fear. It’s the high, fine, beautiful sound of an earth-bound creature who grew wings and flew up high and looked straight into the face of the future. And caught, just for an instant, the unbelievable vision of a free man in a free world.”
—Dalton Trumbo (1905–1976)