Smallest family of subsets that generates the discrete topology

Question

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

Answer 1

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}$.

Answer 2

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.