# (ZF) If $\mathbb{R}^k$ is a countable union of closed sets, then at least one has a nonempty interior

Since the specific space $\mathbb{R}^k$ is given, this might be provable in ZF.

Let $\{F_n\}_{n\in \omega}$ be a family of closed subset of $\mathbb{R}^k$, of which the union is $\mathbb{R}^k$.

Suppose $\forall n\in \omega, {F_n}^o=\emptyset$ ($o$ denotes interior)

Fix $x_0 \in \mathbb{R}^k$ Then by assumption, $\forall 0<r\in \mathbb{R}$, there exists $y\in \mathbb{R}^k$ such that $y\in B(r,x_0)\setminus (F_n \cup \{x_0\})$ for every $n\in \omega$.

I tried to show that for every $r$, there exists $y\in \mathbb{Q}^k$ that satisfies the condition. (Once the existence is guaranteed, since $\mathbb{Q}^k$ can be well-ordered lexicographically, $y$ can be chosen uniquely, hence recursion theorem would be appliable)

But i couldn't. Is there any way to show this?

If it is true, let $y_0 \in B(r,x)\setminus (F_0 \cup \{x_0\})$ and $y_{n+1} \in B(d(y_n,x_0),x_0) \setminus (F_{n+1} \cup \{x_0\})$.

Then, $\forall n\in \omega$, $B(d(y_n,x_0),x_0) \setminus (F_{n+1} \cup \{x_0\})$ is nonempty.

Here, again, i don't know how to show that 'there exists $y\in \mathbb{R}^k$ such that $y\notin \bigcup_{n\in \omega} F_n$.

If my argument is wrong, please give me a proper proof.

-

This is essentially the Baire category theorem. Indeed in ZF it holds for separable complete metric spaces.

The argument is as follows:

Suppose that $(X,d)$ is a separable complete metric space, and $\{a_k\mid k\in\omega\}=D\subseteq X$ is a countable dense subset.

By contradiction assume that we can write $X=\bigcup F_n$ where $F_n$ are closed and with empty interior, we can further assume that $F_n\subseteq F_{n+1}$.

Define by recursion the following sequence:

1. $x_0 = a_k$ such that $k=\min\{n\mid a_n\notin F_0\}$;
2. $r_0 = \frac1{2^k}$ such that $d(F_0,x_0)>\frac1k$, since $x_0\notin F_0$ such $k$ exists.
3. $x_{n+1} = a_k$ such that $k=\min\{n\mid a_n\in B(x_n,r_n)\setminus F_n\}$;
4. $r_{n+1} = \frac1{2^k}$ such that $d(F_n,x_{n+1})>\frac1k$, the argument holds as before.

Note that $x_n$ is a Cauchy sequence, therefore it converges to a point $x$. If $x\in F_n$ for some $n$, first note that $d(x_k,F_n)\leq d(x_k,x)$, by the definition of a distance from a closed set.

If so, for some $k$ we have that $d(x,x_k)<r_n$, in particular $d(F_n,x_k)<r_n$. First we conclude that $n<k$, otherwise $d(F_n,x_n)>r_n$. Now we note that:

$$d(F_n,x_n)\leq d(x,x_n)\leq d(x,x_k)+d(x_k,x_n)\leq r_n+r_n=2r_n$$

It is not hard to see that $2r_n< d(F_n,x_n)$, which is a contradiction to the choice of $x_n$.

Added: Why is there $a_k$ in every step of the inductive definition?

Note that $D$ is dense therefore $\overline{D}=X$. In particular, if $F_n$ is closed and has a dense subset then $F=X$. Since we assume that the interior of $F_n$ is empty we have that $F_n\cap D$ is not dense in $X$, otherwise $F_n=X$ and has a non-empty interior.

We have that $D\setminus F_n$ is dense, since $D\cap F_n$ is not dense. In particular this means that in every open set there is some $a_k\in D\setminus F_n$, and thus the induction can be carried in full.

-
does $d(F_n,x_n)$ mean $d(z,x_n) \forall z\in F_n$? –  Katlus Aug 12 '12 at 22:53
@Katlus: If $A\subseteq X$ is a non-empty set then $d(A,x)=\inf\{d(a,x)\mid a\in A\}$. If $A$ is closed and $X$ is complete then $d(A,x)=0$ if and only if $x\in A$. –  Asaf Karagila Aug 12 '12 at 22:54
Would you give me a hint why $\{n|a_n \notin F_0\} ≠ \emptyset$? –  Katlus Aug 13 '12 at 10:54
@Katlus: If a closed set contains a dense subset of $X$ then it has to contain all the points of $X$, in particular its interior is non-empty. Since we assumed that the interior of $F_n$ is empty it cannot contain a dense subset. –  Asaf Karagila Aug 13 '12 at 11:04
Let $p\in B(x_n,r_n)\setminus F_n$. I showed that 'If $p\notin D$, then $\{k\in \omega|a_k \in B(x_n,r_n)\setminus \{p\}\}≠\emptyset$. Here i don't know how to show that there exists $a_k\in B(x_n,r_n)\setminus F_n$. help! –  Katlus Aug 13 '12 at 12:38

The Baire Category Theorem implies that complete metric spaces are not first category (meager). That is, they are not a countable union of nowhere dense sets. A set $A$ is nowhere dense if $\text{Int}(\bar{A}) = \emptyset$.

Clearly $\mathbb{R}^n$ is a complete separable metric space. If $\mathbb{R}^n = \bigcup_k A_k$ where each $A_k$ is closed and has empty interior, then this contradicts the Baire Category Theorem.

So you just need that the Baire Category Theorem can be proved without the axiom of choice. This is true for Polish Space, i.e. complete separable metric spaces. Theorem 4 from this pdf from Berkeley has short proof of this result : http://math.berkeley.edu/~jdahl/104/104Baire.pdf

-
I think that he is trying to prove BCT for Polish spaces in ZF. Using it here makes no sense. –  Asaf Karagila Aug 12 '12 at 22:03
If I understand the answer, it gives a reference for a proof of BCT in ZF. –  Carl Mummert Aug 12 '12 at 22:17
However, the reference gives proofs "with the axiom of choice" that would not require the axiom of choice if they simply chose the centers of various open balls to be at points from the countable dense subset rather than at arbitrary points. –  Carl Mummert Aug 12 '12 at 22:20
@Carl: The whole question is practically asking for a proof of BCT in the Polish case, without choice. It's fine to reference to a proof off-site, but it's less fine to try and sell it as a different theorem. In particular the first paragraph bothers me. –  Asaf Karagila Aug 12 '12 at 22:33

The answer follows from an application of some descriptive set theory and Shoenfield's absoluteness theorem. The rest of this answer works the same way in $\mathbb{R}^k$ as in $\mathbb{R}$, but I will write it up (shortly) in $\mathbb{R}$ for notational simplicity.

Actually, the principle in question is a variant of the Baire category theorem and would be provable in a very weak subsystem of second-order arithmetic, even if generalized to an arbitrary complete separable metric space. Second-order arithmetic is much much weaker than ZF. So showing that the principle is provable in ZF is much easier, although I am going to just use the big hammer of Shoenfield's absoluteness theorem here.

Here is a sketch in ZF, showing how to apply the absoluteness theorem. The key point is that we have to show that the principle of interest can be expressed by a formula at a low level of the analytical hierarchy.

Note that given any open set $U$, ZF can form the set $A(U) = \{ (i,j) : B(q_i, 2^{-j}) \subseteq U\}$ where $(q_i)$ is some fixed enumeration of the rational points and $B(\cdot,\cdot)$ denotes a ball as usual. And this construction is uniform; given a sequence $(U_i)$, ZF is able to form $(A(U_i))$.

Furthermore, a set is by definition closed if and only if its complement is open.

Thus, in ZF, the statement that the union of a sequence $(C_k)$ of closed sets covers all of $\mathbb{R}$ can be written in the following form:

$$(\forall x \in \mathbb{R})(\exists i, j,k \in\omega)[ (i,j) \in A(U_k) \land d(x, q_i) < 2^{-j}].$$ where $(U_k)$ is the sequence of the open sets complementary to the sets in thbe sequence $(C_k)$.

The displayed formula is at level $\Pi^1_1$ of the analytical hierarchy if $(A(U_k))$ and the distance function are taken as parameters (the parameters can be taken to be elements of $\omega^\omega$ with routine coding, and the quantifier over $\mathbb{R}$ can be replaced with a quantifier over $\omega^\omega$ with routine methods, and the correctness of these methods can be verified in ZF).

Similarly, the statement that some $C_k$ has nonempty interior can be written as

$$(\exists k)(\forall x\in \mathbb{R})(\exists i,j)[ d(x, q_i) < 2^{-j} \to x \in C_k]$$

This is again $\Pi^1_1$ in the analytical hierarchy because we can replace $x \in C_k$ with $x \not \in A(U_k)$ as above. Thus the overall statement "if $\mathbb{R} = \bigcup C_k$ then some $C_k$ has nonempty interior" can be taken, in ZF, to be of the form $(\Pi^1_1) \to (\Pi^1_1)$, and hence this statement is $\Sigma^1_2$ relative to some parameters in $\omega^\omega$.

Shoenfield's absoluteness theorem, which is provable in ZF, states that $\Sigma^1_2$ sentences of the analytical hierarchy with parameters $X \in \omega^\omega$ are absolute - have the same truth value - between $V$ and $L(X)$. Because $L(X)$ provably satisfies ZFC, and ZFC proves the principle in question, ZF can prove that the principle will be true in $L(X)$ and thus also true in $V$ by Shenfield's theorem.

-

Although it’s essentially equivalent to Asaf’s, I prefer the following proof (in ZF) that every separable, completely metrizable space is Baire: I find it easier to work with dense open sets.

Let $\langle X,d\rangle$ be a complete, separable metric space, let $D=\{x_n:n\in\Bbb N\}$ be dense in $X$, let $\{U_n:n\in\Bbb N\}$ be a family of dense open subsets of $X$, and let $V$ be a non-empty open subset of $X$. For $n\in\Bbb N$ and $x\in X$ let $B(x,n)$ be the open $d$-ball of radius $2^{-n}$ centred at $x$, and let $D(x,n)$ be the closed $d$-ball of radius $2^{-n}$ centred at $x$.

Let $$m(0)=\min\left\{n\in\Bbb N:x_n\in G\cap G_0\right\}$$ and $$k(0)=\min\left\{n\in\Bbb N:D\left(x_{m(0)},n\right)\subseteq G\cap G_0\right\}\;.$$

Given $m(n),k(n)\in\Bbb N$, let $$m(n+1)=\min\left\{i\in\Bbb N:x_i\in B\left(x_{m(n)},k(n)\right)\cap G_{n+1}\right\}$$ and $$k(n+1)=\max\left\{2^{n+1},\min\left\{i\in\Bbb N:D\left(x_{m(n+1)},i\right)\subseteq B\left(x_{m(n)},k(n)\right)\cap G_{n+1}\right\}\right\}\;.$$

For $n\in\Bbb N$ let $y_n=x_{m(n)}$. Then

$$B\left(y_n,k(n)\right)\supseteq D\left(y_{n+1},k(n+1)\right)\supseteq B\left(y_{n+1},k(n+1)\right)\supseteq D\left(y_{n+2},k(n+2)\right)\supseteq\ldots$$

for each $n\in\Bbb N$. In particular, $\{y_i:i\ge n\}\subseteq B(y_n,k(n))\subseteq B(y_n,n)$, so $\langle y_n:n\in\Bbb N\rangle$ is a $d$-Cauchy sequence and therefore converges to some $y\in X$. Clearly $y\in D(y_n,k(n))\subseteq G\cap G_n$ for each $n\in\Bbb N$, so $$y\in G\cap\bigcap_{n\in\Bbb N}G_n\ne\varnothing\;.$$ Thus, $\bigcap_{n\in\Bbb N}G_n$ is dense in $X$, and $X$ is Baire.

-
Brian, I agree it's easier. In fact one could simply repeat the proof in Herrlich's book which is quite similar. I wanted to do my best to stay "close" to the original question instead; and I wanted to do something which is not cut-and-paste for my own personal reasons. –  Asaf Karagila Aug 13 '12 at 7:35
@Asaf: Now that you mention it, I may even have been working from an unconscious memory of the proof in Herrlich’s book. I think that it’s good to have both versions available, one for its close relationship to the original question, and one to show that there’s more than one way of looking at it, and that another way might be easier. (Or might not, depending on the individual.) –  Brian M. Scott Aug 13 '12 at 7:44