# Equivalence of countable choice for subsets of the reals and “second countable $\implies$ Lindelöf”

Looking for a proof that in a second countable space every open cover has a countable subcover -- i.e. every s.c. space is a Lindelöf space -- I bumped into this question. That answered my question. I then left a couple of comments on both the then present answers (which are, to this date, the only ones) and received this reply, stating the axiom of countable choice for subsets of the reals is actually equivalent to every s.c. space being Lindelöf. Now it seems incredible that a special case of the axiom of countable choice, which in its general form states any countable collection of sets has a choice function, so for all countable collection of sets $A_n$ there is a function associating to each set an element of that set, provided of course the sets are non-empty, and in its particular form says so for sets which are subsets of the reals, be equivalent to s.c. implies Lindelöf. At most, I would expect the general form to be equivalent to that, since that s.c. implies Lindelöf is proven with a form of countable choice. So how can it be proved that the two results are equivalent?

• It sounds to me like you've interpreted Brian's comment as something like CC($\Bbb R$) $\Rightarrow$ (SC$\to$L)($X$) for any topological space $X$, but it seems to me that he intended the more believable CC($\Bbb R$) $\Rightarrow$ (SC$\to$L)($\Bbb R$). – Eric Stucky Apr 24 '15 at 9:45
• Well the comment says «I just checked: $\mathsf{𝖢𝖢}(\mathbb{R})$ is equivalent to every second countable space being Lindelöf.», so how do you read it that way? – MickG Apr 24 '15 at 9:47
• I mean, let's break that down: $\mathsf{CC}(\mathbb{R})$ (subject) is equivalent to (predicate, in symbols $\iff$), every second countable space being Lindelöf (indirect object, which sounds terribly like $(\mathsf{SC}\implies\mathsf{L})(X)$ for any topological space $X$). What am I missing? @BrianMScott am I reading you right? – MickG Apr 24 '15 at 9:50
• Ah, I missed "every". – Eric Stucky Apr 24 '15 at 9:53
• @Eric: You can find this long lit of equivalences as Theorem 4.54 in Herrlich "The Axiom of Choice". I don't remember the name of the original paper, I think "disasters in topology without choice" or something similar. – Asaf Karagila Apr 24 '15 at 9:55

This is not that incredible if you understand what's going on.

Given a second-countable space $X$, fix a countable basis $\{U_n\mid n\in\Bbb N\}$. Now you can observe that every open set is uniquely determined by the basis elements it contains, namely the function $U\mapsto\{n\in\Bbb N\mid U_n\subseteq U\}$ is an injective function. And since the real numbers can be thought of as subsets of $\Bbb N$, this is an injective function from the topology of $X$ into $\Bbb R$.

So if we are given an open covering, $\{V_i\mid i\in I\}$ we may assume that $|I|\leq|\Bbb R|$ by the above consideration, and for each $n\in\Bbb N$ we can look at the set $A_n=\{V_i\mid U_n\subseteq V_i\}$.

Not every $A_n$ is non-empty, but at least one of them is, of course. By the translation between open sets and real numbers, this is reduced to a countable family of sets of reals. Using $\sf AC_\omega(\Bbb R)$ we can choose from each non-empty $A_n$, and we can prove that this is a countable subcover by noting that $\{U_n\mid A_n\neq\varnothing\}$ is an open cover as well.

On the other hand, if $\{A_n\mid n\in\Bbb N\}$ is a family of pairwise disjoint sets of reals without a choice function. We may assume that each $A_n$ is a subset of $[n,n+1)$ by using canonical bijections of $[\inf A_n,\sup A_n+1)$ and $[n,n+1)$.

Now consider the open covering of $\Bbb R$ defined by $\{(-r,r)\mid\exists n: r\in A_n\}$. Since the $A_n$'s grow arbitrarily large this is an open covering indeed, so by the assumption it has a countable subcover, which gives for each $A_n$ a countable subset, so by diluting this subcover we may assume that each $A_n$ gives at most a single real number.

And therefore we found a partial choice function for the $A_n$'s. Now it is enough to show that it is indeed enough to consider partial choice functions.

Indeed recall that $\Bbb R^{<\omega}$, the finite sequences of real numbers have the same cardinality as $\Bbb R$ itself. Given a sequence of sets $X_n$ which are non-empty, consider $A_n=\prod_{k\leq n}X_n$, then the $A_n$'s are non-empty sets of finite sequences of real numbers, so by uniform encoding we may assume these are sets of real numbers. If $I\subseteq\Bbb N$ is infinite and $\sigma$ is a function choosing from $\{A_i\mid i\in I\}$, then it defines a choice function from the $X_n$ by looking at $i=\min\{j\in I\mid j>n\}$ and looking at $\sigma(i)(n)$ (recall that $\sigma(i)$ is a choice function which is defined on $X_n$).

• @Mick: I've added the needed part. It's a bit half-assed, but if you need more details let me know. – Asaf Karagila Apr 24 '15 at 14:05
• @bof: Thanks for pointing out the missing piece. – Asaf Karagila Apr 24 '15 at 15:18
• So the subcover gives a countable subset of the reals for each $A_n$ by considering $\{r:r\in A_n,(-r,r)\in\text{subcover}\}$, right? What do you mean by «by diluting this subcover»? What is a partial choice function? – MickG Apr 24 '15 at 15:24
• @Mick: No, each $A_n$ is bounded so this set cannot possibly cover $\Bbb R$, but if you take the union over all the $A_n$'s you get a cover (because they live in arbitrarily large $[n,n+1)$ intervals). Then you get a sequence of reals, so pick for each $A_n$ the real with the least index of the countable subcover that appears in $A_n$, if there is such real, there might not be one. But since no single $A_n$ produces a cover, this ensure that we will meet $A_n$ for arbitrarily large $n$, and this gives a choice function for an infinite subset of the $A_n$'s. Hence partial choice. – Asaf Karagila Apr 24 '15 at 15:29
• OK so let me get this straight. You said we consider the cover of $\mathbb{R}$ formed by the $(-r,r)$ such that $r\in A_n$ for some $n$. I agree it's a cover because the $A_n$'s grow arbitrarily large, since we have assumed WLOG $A_n\subseteq[n,n+1)$. So that is a cover. We assumed a second-countable space is Lindelöf and $\mathbb{R}$ is Lindelöf, thus this cover admits a countable subcover $\{(-r_k,r_k)\}$ for $k\in\mathbb{N}$. I was suggesting we could associate $A_n$ with the set of all $r_k\in A_n$. This maps the subsets $A_n$ to countable subsets. That was my guess to see how the finite … – MickG Apr 24 '15 at 16:03

The discrete topology on a countable set is second countable; it has a countable base consisting of the singleton sets. Thus, the assertion that all second countable spaces are Lindelöf implies that every cover of a countable set $N$ by subsets of $N$ has a countable subcover. I will show that the latter (ostensibly weaker) assertion implies $\mathsf{AC}_\omega(\mathbb R)$, the countable axiom of choice for sets of real numbers.

Assume that every collection of subsets of $\mathbb Q$ which covers $\mathbb Q$ has a countable subcover. Let $(X_n:n\in\mathbb N)$ be a family of nonempty subsets of $\mathbb R$; I will show that the Cartesian product $\prod_{n\in\mathbb N}X_n$ is nonempty.

For each $x\in\mathbb R,$ let $$L_x=(\mathbb Q\setminus\mathbb N)\cap(-\infty,x).$$ Now define $$\mathcal U=\{\mathbb Q\setminus\mathbb N\}\cup\{\{n\}\cup L_x:n\in\mathbb N,\ x\in X_n\}.$$ Since $\bigcup\mathcal U=\mathbb Q$, there is a countable subfamily $\mathcal U'$ of $\mathcal U$ which also covers $\mathbb Q.$ For each $n\in\mathbb N,$ let $U_n$ be the first element of $\mathcal U'$ (relative to some fixed enumeration) which covers $n.$ Then $U_n=\{n\}\cup L_x$ for some $x\in X_n.$ Thus we can define $x_n=\sup(U_n\setminus\{n\})\in X_n$ and we will have $(x_n:n\in\mathbb N)\in\prod_{n\in\mathbb N}X_n.$

• Very interesting alternate way of proving one implication, I'd say easier than Asaf's. Still, I keep his answer as accepted because it is complete :). +1 anyway. – MickG Apr 24 '15 at 22:12

Let $\mathcal B$ be the countable base of $X$. Then for any open cover $\mathcal U=\{U_\alpha:\alpha \in \Omega\}$, then for any $x\in X$ and $x \in U_\alpha$, there exists $B_x\in \mathcal B$ such that $x\in B_x \subset U_\alpha$. Then $\{B_x:x\in X\}$ is the subcover and countable.

• I have the impression this is merely a proof that second countable implies Lindelöf. I am not asking for this proof. I am asking how it can be proved that the proposition "second countable implies Lindelöf" is equivalent to countable choice for subset of the reals, or in short $\mathsf{CC}(\mathbb{R})$, which is what @BrianMScott stated in the comment I linked to in teh question. – MickG Apr 24 '15 at 9:05