Editing Distributive lattice (section)

== Free distributive lattices ==
[[File:Monotone Boolean functions.svg|thumb|360px|Free distributive lattices on zero, one, two, and three generators. The elements labeled "0" and "1" are the empty join and meet, and the element labeled "majority" is (''x'' ∧ ''y'') ∨ (''x'' ∧ ''z'') ∨ (''y'' ∧ ''z'') = (''x'' ∨ ''y'') ∧ (''x'' ∨ ''z'') ∧ (''y'' ∨ ''z'').]]

The [[free object|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 <math>\lor</math> and <math>\land</math> on a set of generators can be transformed into the following equivalent ''normal form'':

:<math>M_1 \lor M_2 \lor \cdots \lor M_n,</math>

where <math>M_i</math> are finite meets of elements of ''G''. Moreover, since both meet and join are [[associative]], [[Commutativity|commutative]] and [[Idempotence|idempotent]], one can ignore duplicates and order, and represent a join of meets like the one above as a set of sets:

:<math>\{N_1, N_2, \ldots, N_n\},</math>

where the <math>N_i</math> 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 <math>N_j</math> is a subset of <math>N_k.</math> In this case the meet of <math>N_k</math> will be below the meet of <math>N_j,</math> and hence one can safely remove the ''redundant'' set <math>N_k</math> 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 <math>N_i</math> are mutually incomparable (with respect to the subset ordering); that is, when it forms an [[Sperner family|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 <math>\{N \cup M \mid N \in S, M \in T\}.</math> 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 number]]s. These numbers grow rapidly, and are known only for ''n''&nbsp;≤&nbsp;9; they are
:2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, 286386577668298411128469151667598498812366 {{OEIS|id=A000372}}.
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, 286386577668298411128469151667598498812364 {{OEIS|id=A007153}}.