TransWikia.com

Smallest family of subsets that generates the discrete topology

MathOverflow Asked by user175348 on November 3, 2021

If $X$ is a finite set, what is the smallest (in cardinality) family of open subsets $mathcal Usubseteq 2^X$ such that $mathcal U$ generates the discrete topology, i.e. if $mathcal Usubseteq tausubseteq 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 $xin X$ there should exist a set $I(x)subset {1,ldots,k}$ such that $cap_{iin I(x)} A_i={x}$. Note that $I(x)$ is not contained in $I(y)$ for $xne y$. Therefore $|X|leqslant binom{k}{lfloor k/2rfloor}$ by Sperner's theorem. On the other hand, if $|X|leqslant binom{k}{lfloor k/2rfloor}$, we may construct an injection $f$ from $X$ to $lfloor k/2rfloor$-subsets of ${1,ldots,k}$ and define $A_i={x:iin f(x)}$. Then $cap_{iin f(x)} A_i={x}$.

So the answer is the minimal $k$ for which $|X|leqslant binom{k}{lfloor k/2rfloor}$.

Answered by Fedor Petrov on November 3, 2021

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.

Answered by Florian Lehner on November 3, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP