12
$\begingroup$

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

$\endgroup$

2 Answers 2

17
$\begingroup$

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

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
1
  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.