The number of families of subsets that are closed with respect to intersections

V. B. Alekseev

Diskretnaya Matematika, Tome 1 (1989) no. 2, pp. 129-136

Résumé

Let $\alpha(n)$ be the number of families of subsets of an $n$-element set having the property: for every two subsets of the family, their intersection belongs to the family as well. In this article it is proved that $\log_2\alpha(n)\sim C_n^{[n/2]}$ as $n\to\infty$. It follows from this that the same result is also valid for some other structures, in particular for the number of all possible closure operations on an $n$-element set. These results are obtained as a corollary of the analogous result as $n\to \infty$ and $k=o(\sqrt n/\log_2^2n)$ for the number of families of subsets of an $n$-element set which satisfy the condition: if $k$ one-element extensions of a subset $A$ belong to the family, then $A$ belongs to the family as well. Since there is a correspondence between families of subsets and functions of logic algebra, these results establish also asymptotics of the logarithm for the number of functions of the logic algebra of $n$ variables with the corresponding properties.