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:
“This leads us to note down in our psychological chart of the mass-man of today two fundamental traits: the free expansion of his vital desires, and, therefore, of his personality; and his radical ingratitude towards all that has made possible the ease of his existence. These traits together make up the well-known psychology of the spoilt child.”
—José Ortega Y Gasset (1883–1955)