# Smallest family of subsets that generates the discrete topology

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$$?

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}$$.
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.
• 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? Jul 16, 2020 at 2:24