Do we need full choice to "efficiently" use (sub)bases?

Question

This question was previously asked and bountied at MSE without success.

---

Suppose $(X,\tau)$ is a topological space, $B$ is a base for $\tau$, and $U\in \tau$ is an open set. Consider the following two strategies for writing $U$ as a union of elements of $B$:

• We have $U=\bigcup\{V\in B: V\subseteq U\}$.

• For each $u\in U$ pick some $V_u\in B$ with $u\in V_u\subseteq U$; then $U=\bigcup\{V_u: u\in U\}$.

The first strategy has the advantage of not requiring the axiom of choice. If we pay attention to the number of basic opens required, however, it is noticeably inefficient: the first strategy might involve as many as $2^{\vert U\vert}$-many basic open sets, while the second involves at most $\vert U\vert$-many.

It's not hard to show that in fact this drop in efficiency is unavoidable: it is consistent with $\mathsf{ZF}$ that there is a space $(X,\tau)$, a base $B$ for $\tau$, and an open set $U\in\tau$ such that there is no map $f:U\rightarrow B$ with $\bigcup_{u\in U}f(u)=U$. I'm interested in the exact strength of the corresponding efficiency principle, as well as its "subbase" variation:

Over $\mathsf{ZF}$, are either of the following statements equivalent to $\mathsf{AC}$?

• For every topological space $(X,\tau)$, every base $B$ for $\tau$, and every $U\in\tau$, there is some $f:U\rightarrow B$ with $\bigcup_{u\in U}f(u)=U$.
• For every topological space $(X,\tau)$, every subbase $B$ for $\tau$, and every $U\in\tau$, there is some $f:U\rightarrow [B]^{<\omega}$ with $\bigcup_{u\in U}(\bigcap f(u))=U$.

(Above, "$[A]^{<\omega}$" denotes the set of finite subsets of $A$. So the subbase version of the principle is saying that we can write $U$ as the union of $U$-many finite intersections of subbase elements.)

EDIT: I do not require that $u\in f(u)$ (resp. $u\in\bigcap f(u)$) in the principles above, although that is a very natural requirement to include.

Answer 1

EDIT: this answer addresses a variant of this question in which we require that $u\in f(u)$, respectively $u\in\bigcap f(u)$. Unfortunately it doesn't seem to say anything about the question as stated.

The subbase version implies AC. Let $X_i,i\in I$ be a family of nonempty sets. We may assume they are pairwise disjoint and are disjoint from $I$, and that $|X_i|>1$ for all $i$. Define a topology on $I\cup\bigcup_{i\in I}X_i$ by taking a subbasis $B$ consisting of sets $\{i,x\}$ for all $x\in X_i$. Then $I$ is an open subset in this topology: indeed, for any $i\in I$ and distinct $x,y\in X_i$ we have $\{i\}=\{i,x\}\cap\{i,y\}$.

Now any function $f:I\to[B]^{<\omega}$ such that $I=\bigcup_i(\bigcap f(i))$ and $i\in f(i)$ must satisfy that $f(i)$ consists of (finitely many) sets of the form $\{i,x\}$, and so $\bigcup f(i)\setminus\{i\}$ is a nonempty finite subset of $X_i$. We conclude that axiom of multiple choice holds, and hence so does axiom of choice.

Update: the basis version also implies (multiple) choice. Take the same set $X=I\cup\bigcup_{i\in I}X_i$ as above, but this time take the following basis of a topology: we take $B$ to consist of sets of the form $\{i\}\cup A$, where $A$ is a proper subset of $X_i$ whose complement in $X_i$ is finite. Any two elements of $B$ are either disjoint or their intersection is in $B$ as well. As $\bigcup B=X$, this implies $B$ is a basis of a topology. In particular $X$ itself is a union of elements of $B$. Let $f:X\to B$ be a function such that $x\in f(x)$ for all $x$. Then $X_i\setminus f(i)$ is a nonempty finite subset of $X_i$, giving multiple choice.

Answer 2

Too long for a comment, so I provide a (very partial) answer.

The short version: I cannot answer your question directly, but I can provide examples of much weaker systems where something very similar happens, even at the level of WKL$_0$ or ACA$_0$. In particular, some form of choice is needed to work with sub-bases in weak systems.

The long version: In higher-order Reverse Mathematics, working over RCA$_0^\omega$ from [0], the following compactness and local-global principle are equivalent (as they should be):

(a) WKL

(b) Pincherle's theorem: a locally bounded function on $2^{\mathbb{N}}$ is bounded there.

given countable choice for quantifier-free formulas, called $\textsf{QF-AC}^{0, 1}$ by Kohlenbach in [0].

One can also show that Z$_2^\omega$ alone cannot prove item (b), where the former is a conservative extension of second-order arithmetic Z$_2$ with third-order functionals $S_k^2$ that can decided $\Pi_k^1$-formulas from L$_2$. On the other hand, Z$_2^\Omega\equiv $ RCA$_0^\omega+(\exists^3)$ can prove item (b), where the former is also conservative over Z$_2$. All these results are in [1], with all definitions explained.

As you can see, Pincherle's theorem is rather weak/easy to prove given countable choice, but in the absence of the latter, becomes hard to prove. Dag and I refer to the above observation as the `Pincherle phenomenon': given a little bit of AC, one obtains the expected RM-equivalences to weak principles. Without any AC, one has to break out rather strong systems to prove the theorem at hand. Many examples of the Pincherle phenomenon can be found in [2,3].

As it happens, the Pincherle phenomenon is also exhibited by the following theorem (A):

(A) any open set in $\mathbb{R}$ is a countable union of basic open intervals

In a nutshell, given the aforementioned choice principle QF-AC$^{0,1}$, one proves this theorem (A) in a system at the level of ACA$_0$. On the other hand, Z$_2^\omega$ cannot prove this theorem (A). So working with sub-bases seems to require some kind of fragment of choice.

Finally, a weaker choice principle, called NCC and provable in ZF, suffices for the above results. as explored in [2].

References

[0] U. Kohlenbach, Higher order reverse mathematics, Reverse mathematics 2001, Lect. Notes Log.,vol. 21, ASL, 2005, pp. 281–295.

[1] D. Normann and S. Sanders, Pincherle’s theorem in reverse mathematics and computability theory, Ann. Pure Appl. Logic 171 (2020), no. 5, 102788, 41.

[2] ____, The Axiom of Choice in Computability Theory and Reverse Mathematics, To appear in Journal of Logic and Computation (2021), pp. 25.

[3] ____, Open sets in Reverse Mathematics and Computability Theory, Journal of Logic and Computability 30 (2020), no. 8, pp. 40.