Dedekind Number - Definitions

Definitions

A Boolean function is a function that takes as input n Boolean variables (that is, values that can be either false or true, or equivalently binary values that can be either 0 or 1), and produces as output another Boolean variable. It is monotonic if, for every combination of inputs, switching one of the inputs from false to true can only cause the output to switch from false to true and not from true to false. The Dedekind number M(n) is the number of different monotonic Boolean functions on n variables.

An antichain of sets (also known as a Sperner family) is a family of sets, none of which is contained in any other set. If V is a set of n Boolean variables, an antichain A of subsets of V defines a monotone Boolean function f, where the value of f is true for a given set of inputs if some subset of the true inputs to f belongs to A and false otherwise. Conversely every monotone Boolean function defines in this way an antichain, of the minimal subsets of Boolean variables that can force the function value to be true. Therefore, the Dedekind number M(n) equals the number of different antichains of subsets of an n-element set.

A third, equivalent way of describing the same class of objects uses lattice theory. From any two monotone Boolean functions f and g we can find two other monotone Boolean functions f ∧ g and f ∨ g, their logical conjunction and logical disjunction respectively. The family of all monotone Boolean functions on n inputs, together with these two operations, forms a distributive lattice, the lattice given by Birkhoff's representation theorem from the partially ordered set of subsets of the n variables with set inclusion as the partial order. This construction produces the free distributive lattice with n generators. Thus, the Dedekind numbers count the number of elements in free distributive lattices.

The Dedekind numbers also count the number of abstract simplicial complexes on n elements, families of sets with the property that any subset of a set in the family also belongs to the family. Any antichain determines a simplicial complex, the family of subsets of antichain members, and conversely the maximal simplices in a complex form an antichain.