Given a countable subbase of a topology, we can consider its complexity in terms of the difficulty of determining whether one family of basic open sets covers another basic open set. My question is about the extent to which a second-countable space can have different subbases of (relatively) wildly different levels of complexity. At high enough complexity the answer becomes "not meaningfully," but the situation is less clear for spaces with simpler presentations.

Fixing a countable subbase $\mathcal{B}=(B_i)_{i\in\omega}$ of a topology $\tau$ (we'll never be interested in the actual set of points), we can define the (atomic) covering problem for $\mathcal{B}$: $$cp(\mathcal{B})=\{\langle i, J\rangle\in \omega\times 2^\omega: B_i\subseteq\bigcup_{j\in J}B_j\}.$$ Ultimately, I'm interested in how complexity of the covering problem can be reflected in other aspects of the space, so a natural thing to do now is to look at its descriptive set theoretic complexity.

Now unfortunately this is really about the subbase, not the space - different countable subbases can yield different complexity covering problems (although as long as we look at the "boldface" picture, the order in which we enumerate the subbase is irrelevant). For example, while the covering problem of the usual base for Cantor space is open, we can get a subbase whose covering problem is $\Pi^0_2$ by adding any non-compact open set to the usual base.

Luckily, however, there are bounds on how much the complexity of the covering problem can change from subbase to subbase. For example, in the Cantor space case above (or indeed any space with a countable base of compact sets) it's easy to see that every subbase has covering problem at worst $\Pi^0_2$. More generally, it's not hard to show that the covering problems of two different subbases of the same space can only be "off by $\Delta^1_1$" of each other - so, for example, any countable subbase for Baire space has $\Pi^1_1$ covering problem.

However, this is silly from the Borel point of view. My question is whether in fact we can see true wildness within this restricted context:

Is there a second-countable topology $\tau$ which has subbases with covering problems arbitrarily high in the Borel hierarchy (but still Borel)?

EDIT: To show that this question isn't vacuous (and justify bountying it back to the "front page"), here's a basic construction for producing covering problems of prescribed complexity (which in particular can give covering problems at all levels of the Borel hierarchy):

Say that $\mathcal{U}\subseteq \mathcal{P}(\omega)$ is an up-set if, well, it's closed upwards and (for non-triviality) is neither $\emptyset$ nor $\mathcal{P}(\omega)$. Now fix an up-set $\mathcal{U}$. We let $$U_0=\mathcal{P}(\omega)\setminus \mathcal{U},\quad U_{i+1}=\{A\in\mathcal{P}(\omega)\setminus \mathcal{U}: i\not\in A\}.$$ The family $\{U_i:i\in\omega\}$ forms a subbase $\mathcal{S}$ for a topology on $\mathcal{P}(\omega)\setminus\mathcal{U}$; I claim that the covering problem of this subbase is of the same complexity as the up-set $\mathcal{U}$ and so we can control the covering problem by finding up-sets of desired complexity.

In one direction, we have $$A\in\mathcal{U}\iff \langle 0,\{a+1: a\in A\}\rangle\in cp(\mathcal{S}),$$ so we can reduce $\mathcal{U}$ to $cp(\mathcal{S})$. Conversely, we have $$\langle i, A\rangle\in cp(\mathcal{S})\iff \mbox{ either $i\not=0$ and $i-1\in A$, or $A\in\mathcal{S}$.}$$ This gives a reduction of $cp(\mathcal{S})$ to $\mathcal{U}$.

So we can reduce the task of finding subbases of topologies with covering problems of a desired level of complexity to the task of finding appropriately complicated up-sets, which is much easier. For example, from the up-set $$\mathcal{U}=\{A: \forall i_1\exists i_2\forall i_3\exists i_4(A_{\langle i_1,i_2,i_3,i_4\rangle}\not=\emptyset)\}$$ (where $\langle\cdot,\cdot,\cdot,\cdot\rangle$ is an appropriate $4$-tupling operation) we get a subbase whose covering problem is properly $\Pi^0_4$.

Now admittedly, as far as I can tell this isn't even slightly useful for the specific question above, but it does suggest that the situation isn't totally boring.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.