RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 1989 Volume 1, Issue 2, Pages 129–136 (Mi dm915)

This article is cited in 2 papers

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

V. B. Alekseev


Abstract: 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.

UDC: 510.716

Received: 15.11.1988



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025