How much can complexities of bases of a "simple" space vary?

Question

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.

Answer 1

Welp, this wasn't my finest moment: unless I'm missing something, we can translate everything much more easily than I thought at first. (I may indeed be missing something, however, and I'll wait a while before accepting this just in case.)

For simplicity I'll look at bases only; it won't make a serious difference.

Suppose I have enumerated bases $\mathcal{B}_1=(B^1_i)_{i\in\omega},\mathcal{B}_2=(B^2_i)_{i\in\omega}$ for the same topology and $cp(\mathcal{B}_2)\in{\bf\Gamma}$ (here ${\bf\Gamma}$ is a Borel complexity class and we're viewing a covering problem as a set of reals in the obvious way). I claim that $cp(\mathcal{B}_1)\in {\bf\Pi^0_1\Gamma\Sigma^0_1}$ - so e.g. if $cp(\mathcal{B}_2)$ were $\bf \Sigma^0_4$ we would know that $cp(\mathcal{B}_1)$ is $\bf \Pi^0_1\Sigma^0_4\Sigma^0_1=\Pi^0_6$ at worst. A bit more interestingly, since the usual base for Cantor space has covering problem in $\bf\Sigma^0_1$, this shows that the example in the question is maximally complicated: we can't do worse than $\bf\Pi^0_1\Sigma^0_1\Sigma^0_1=\Pi^0_2$.

OK yeah that notation is horrible, but it should be clear what I mean and I don't know how to write it better.

I'll present the proof, then a couple comments, then mention a couple natural further questions (which I think are interesting enough to include but aren't really "MO-ready").

---

The proof is as follows:

First, we look at representing $cp(\mathcal{B}_2)$ more explicitly. Since $\bf\Gamma\subseteq\Delta^1_1$, we have a code for $cp(\mathcal{B}_2)$; namely, a well-founded tree $T\subseteq\omega^{<\omega}$ together with a labelling of the nodes of $T$, where each non-leaf is labelled either with $\bigwedge$ or $\bigvee$ (and this results in the appropriate "quantifier complexity") and each leaf is labelled with a formula - in the language consisting of $(i)$ a constant symbol $\underline{n}$ for each natural number $n$, $(ii)$ $=$, $\not=$, and $\in$ (see below re: why no "$\not\in$"), and $(iii)$ a "number variable" $\alpha$ and a "set variable" $\Upsilon$ - of one of the following forms:

• $\underline{n}=\alpha$ for some $n\in\omega$.

• $\underline{n}\not=\alpha$ for some $n\in\omega$

• $\underline{n}\in \Upsilon$ for some $n\in\omega$.

  • For example, let $T$ be the tree consisting of a root with $\omega$-many children, each of which has two children each of which is a leaf; label the root of $T$ with "$\bigwedge$," label each child of the root with "$\bigvee$," label the first child of the $i$th root with "$\underline{i}\not=\alpha$," and label the second child of the $i$th root with "$\underline{i}\in\Upsilon$." Intuitively this says "if $\alpha=i$ then $i\in \Upsilon$," or more naturally "$\alpha\in\Upsilon$," and this describes the "trivial" situation when the basic open sets are disjoint: $\langle i,J\rangle$ is in the covering problem iff $i\in J$.

Key observation: note that we've left out the form "$\underline{n}\not\in\Upsilon$" - this is because we can freely do without it, since $cp(\mathcal{B}_2)$ is monotonic (we can't stop covering by adding more sets). More precisely, there is a code of the above form.

Next, we set up our translation. Let $$t=\{\langle a,b\rangle: B_a^2\subseteq B_b^1\}$$ be the obvious "translation" parameter; this induces a map $$\mathbb{F}: \mathcal{P}(\omega)\rightarrow\mathcal{P}(\omega): H\mapsto\{k: \exists h\in H(\langle k,h\rangle\in t)\}.$$

We then observe that $$\langle i,J\rangle\in cp(\mathcal{B}_1)\iff \forall l(\langle l,i\rangle\in t\rightarrow \langle l,\mathbb{F}(J)\rangle\in cp(\mathcal{B}_2)).$$ Since being in the output of $\mathbb{F}$ is an existential condition and leaves in our Borel code for $cp(\mathcal{B}_2)$ only refer to the "set-part" positively, we're just turning some of the leaves in that code to existential statements; and all of this is bracketed inside a universal quantifier. So we get $$cp(\mathcal{B}_1)\in\bf\Pi^0_1\Gamma\Sigma^0_1$$ as desired.

---

A couple comments on the argument above:

First, note that without the key observation, our translation would be a bit worse: we'd only get $$cp(\mathcal{B}_1)\in\bf\Pi^0_1\Gamma(\Sigma^0_1\wedge\Pi^0_1).$$

Second, what if we're looking at a covering problem which isn't Borel? The approach above crucially used the "shape" of Borel codes. I don't see how to do any better in general than the coarse bound from the question.

---

Finally, let me mention a couple natural remaining questions:

• Does every second-countable space have a base with least complicated covering problem? What about most complicated?

  • Towards the latter, we can certainly "amalgamate" countably many bases, but that doesn't actually seem to help; and I have no idea whatsoever about the former.

• Is the set of complexities of covering problems "convex"? E.g. if $(X,\tau)$ has bases with covering problems $\bf\Sigma^0_7$ and $\bf \Sigma^0_9$, need it have a base with covering problem $\bf\Sigma^0_8$?

  • The answer should be a fairly easy "yes" - take "part of" the more complicated base and just add it to the simpler base - but I don't see the details.

• And what happens to the above questions if we restrict attention to spaces with Borel covering problems (which may yield a substantially nicer picture)?

• Finally, the examples of spaces I know with Borel covering problem "well above" $\bf\Pi^0_2$ are basically just those in the OP, which are extremely unnatural. Are there any natural examples? What about Hausdorff examples (the only ideas I have all ruin separation properties - even $T_1$).

---

EDIT: at the risk of beating a dead horse, let me add what I think is the "right" way to view the situation:

The covering problem is actually the wrong object to look at. Given an enumerated base $\mathcal{B}=(B_i)_{i\in\omega}$ for a space $(X,\tau)$ with $B_0=\emptyset$, let the equality problem be the set $$eq(\mathcal{B})=\{\langle f,g\rangle\in (2^\omega)^2: \bigcup_{i\in I}B_{f(i)}=\bigcup_{j\in J}B_{f(j)}\}.$$

The reason to prefer the equality problem over the covering problem is that the former is truly base-invariant. Let $H:\omega^\omega\rightarrow\omega^\omega$ be the map sending $f\in\omega^\omega$ to the sequence $g\in\omega^\omega$ whose $\langle a,b\rangle$th term is $0$ if $B^2_b\not\subseteq B^1_{f(a)}$ and is $j$ otherwise. Then we have $$\bigcup_{i\in\omega}B_{f(i)}^1=\bigcup_{j\in\omega}B^2_{g(j)},$$ and the map $H$ is continuous. With one small additional assumption on the bases we're looking at - e.g. that $B_1$ is also $\emptyset$ - we can make $H$ injective as well. So by looking at equality problems, we actually get a well-defined way to assign to a second-countable space $\mathcal{X}$ a degree d in the partial ordering of equivalence relations on Baire space under continuous embeddability. Meanwhile, note that our comparison of covering problems above was of a fundamentally more complicated type - we reduced a single question in one covering problem to countably many questions in the other.

This doesn't make covering problems uninteresting in my opinion, but I think it does pin down the "right" invariant that the intuition behind this question was ultimately after.