If $X$ is a finite set, what is the smallest (in cardinality) family of open subsets $\mathcal U\subseteq 2^X$ such that $\mathcal U$ generates the discrete topology, i.e. if $\mathcal U\subseteq \tau\subseteq 2^X$ and $\tau$ is a topology, then $\tau=2^X$?
2 Answers
Let $\mathcal{U}=\{A_1,\ldots,A_k\}$. Then for any element $x\in X$ there should exist a set $I(x)\subset \{1,\ldots,k\}$ such that $\cap_{i\in I(x)} A_i=\{x\}$. Note that $I(x)$ is not contained in $I(y)$ for $x\ne y$. Therefore $X\leqslant \binom{k}{\lfloor k/2\rfloor}$ by Sperner's theorem. On the other hand, if $X\leqslant \binom{k}{\lfloor k/2\rfloor}$, we may construct an injection $f$ from $X$ to $\lfloor k/2\rfloor$subsets of $\{1,\ldots,k\}$ and define $A_i=\{x:i\in f(x)\}$. Then $\cap_{i\in f(x)} A_i=\{x\}$.
So the answer is the minimal $k$ for which $X\leqslant \binom{k}{\lfloor k/2\rfloor}$.
Here is a construction that is within a constant factor of optimal.
You can find such an $\cal U$ containing $2 \lceil \log_2 X\rceil $ sets: identify $X$ with a subset of $\{0,1\}^{\lceil \log_2 X\rceil}$ and take $U_i$ to be the set of all elements whose $i$th coordinate is $0$, and $V_i$ to be the set of all elements whose $i$th coordinate is $1$. Then each singleton is an intersection of appropriate sets $U_i$ and $V_i$, so the generated topology includes all singletons and thus is discrete.
On the other hand, we cannot do much better than that: if $\cal U$ contains fewer than $\log_2 X$ sets, then there are two points contained in exactly the same sets of $\cal U$ (and clearly these points cannot be distinguished by the resulting topology). To find such a pair, let $U_1,U_2,\dots$ be an enumeration of the elements of $\cal U$. Let $X_1 = X$ and inductively let $X_{i+1}$ be the larger set of $X_i \cap U_i$ and $X_i \setminus U_i$. Note that in every step we keep at least half of the elements, hence the last $X_i$ contains at least two elements.

1$\begingroup$ Connecting this up with Fedor's answer we have ${2n \choose n} \approx \frac{4^n}{\sqrt{\pi n}}$ so the optimal $\mathcal{U}$ Fedor constructs has just a bit more than $\log_2 X$ sets, something like $\log_2 X + \frac{1}{2} \log_2 \log_2 X$ ish? $\endgroup$ Jul 16, 2020 at 2:24