Every uncountable Polish Space has a copy of $\{0, 1\}^\mathbb{N}$

Question

I am having trouble verifying corollary 7.8 on p. 6 in this document

http://www.math.ucla.edu/~biskup/275b.1.13w/PDFs/Standard-Borel-Spaces.pdf

My troubles are with the definition of the "tree" sequence of balls. Particularly, I don't see the claims at the bottom of the second to last paragraph, saying that $B_{\sigma0}$ is disjoint from $B_{\sigma1}$ and both are contained in $B_{\sigma}$. There are a number of typos in this proof that I think I have figured out. I believe symbols like "$\sigma0$" to denote concatenation. There are a few missing "$\in$"s. I have not figured out what he really means in the definition of $r_n$, which I imagine is part of the hindrance in me being unable to prove the claims mentioned above. Anything addressing these questions would be useful, but I am sufficiently confused such that a rewrite of the proof starting from the point where he constructs the balls and ending at the point where he makes the disjointness and containment claims would be useful. In any case, I certainly would like to be told what the $r_n$ means and why it makes the disjointness and containment claims true, hence the "tree" aspect of the construction. Thanks.

Answer 1

$\newcommand{\BIN}{0\mathord{-}1}$Instead of going through the proof you are reading, I'll give my own outline with some added notes that hopefully clarify the steps. (I will follow the notes and use juxtaposition for concatenation.) There should be a natural translation between the ideas given below and those in the .pdf. In broad outline, what we want to do is the following:

• Without loss of generality assume that $X$ is perfect, i.e., has no isolated points, and is given a complete compatible metric.
• Inductively on the length of a finite $\BIN$ sequence $\sigma$ we define $x_\sigma , r_\sigma$ so as to satisfy the following:
  1. $x_{\sigma 0 } , x_{ \sigma 1} \in B ( x_\sigma ; r_\sigma )$;
  2. $0 < r_\sigma \leq 2^{-|\sigma|}$, where $| \sigma|$ denotes the length of $\sigma$;
  3. $B ( x_{\sigma i } ; r_{\sigma i} ) \subseteq B ( x_\sigma , r_\sigma )$ for $i = 0 ,1$;
  4. $\overline{ B ( x_{\sigma 0 } ; r_{\sigma 0} ) } \cap \overline{ B ( x_{\sigma 1 } ; r_{\sigma 1} ) } = \emptyset$;

Defining $x_\emptyset$ and $r_\emptyset$ poses no problems, so suppose that $x_\sigma$ and $r_\sigma$ have been defined. Note that since $x_\sigma$ is not an isolated point of $X$, then the ball $B ( x_\sigma , r_\sigma )$ contains infinitely many points of $X$, so pick any two distinct ones, and name them $x_{\sigma 0 } , x_{\sigma 1}$. Clearly $d ( x_{\sigma 0} , x_{\sigma 1} ) > 0$, and so let's pick $$r_{\sigma i} = \min \left\{ 2^{|\sigma|+1} , \frac{d ( x_{\sigma 0} , x_{\sigma 1})}3 , r_\sigma - d ( x_\sigma , x_{\sigma i} ) \right\}.$$ Looking at this definition carefully, we see the following:

• Clearly $r_{\sigma i} \leq 2^{-| \sigma | + 1} = 2^{-| \sigma i|}$, so we satisfy (2) above;
• Letting $r = d ( x_{\sigma 0} , x_{\sigma 1} )$, as $r_{\sigma 0} , r_{\sigma 1} \leq \frac{r}{3}$ we will have that $\overline{ B ( x_{\sigma i} ; r_{\sigma i} ) } \subseteq \overline{B} ( x_{\sigma i} \frac{r}{3} )$ (the closed ball), and so these will be disjoint, meaning (4) above is satisfied;
• As $r_{\sigma i} \leq r_\sigma - d ( x_\sigma , x_{\sigma i} )$ by the triangle inequality we will have $B ( x_{\sigma i} , r_{\sigma i} ) \subseteq B ( x_\sigma , r_\sigma )$, and so (3) is satisfied.

Now, given any infinite $\BIN$-sequence $\tau$, for each $n \in \mathbb{N}$ denote by $\tau \restriction n$ the $n$-length $\BIN$-sequence consisting of the first $n$ coordinates of $\tau$. By conditions (2) and (3) above it follows that $\langle x_{\tau \restriction n} \rangle_{n \in \mathbb{N}}$ is a Cauchy sequence in $X$, and therefore converges to some $x _\tau \in X$. Furthermore, if $\tau , \theta$ are distinct infinite $\BIN$-sequences, then there is a minimal $n$ such that $\tau (n) \neq \theta (n)$. It follows that, without loss of generality, $\tau \restriction (n+1) = \sigma 0$ and $\theta \restriction ( n+1) = \sigma 1$ for some finite $\BIN$-sequence $\sigma$. By (3) it will follows that $x_\tau \in \overline{ B ( x_{\sigma 0} , r_{\sigma 0} ) }$ and $x_\theta \in \overline{ B ( x_{\sigma 1} , r_{\sigma 1} )}$ and by (4) it follows that $x_\tau \neq x_\theta$.

Answer 2

I apologise for adding an extra answer, but I have gone through the proof in the linked .pdf, and I believe there is a very good reason to be wary of it. Below I have quoted the relevant part of the proof, using bold italics to denote words/phrases I feel have been omitted, and using $\color{blue}{\text{blue}}$ to denote mathematical symbols I also feel were omitted. Following the quote I given what I feel is the major problem with the proof, which also indicates why you were having such problems with it!

Let $( x_n )$ be a countable dense set (of distinct points) in $\mathcal{P}$. As is easily checked, there exist two functions $f_0$ and $f_1$ from $\{ x_1 , \ldots \}$ to itself such that $$\max \{ d ( f_0 ( x_n ) , x_n ) , d ( f_1 ( x_n ) , x_n ) \} \leq 2^{-n} \tag{7.19}$$ and $$\min \{ d ( f_0 ( x_n ) , x_n ) , d ( f_1 ( x_n ) , x_n ) \} \geq d ( f_0 ( x_n ) , f_1 ( x_n ) ) > 0. \tag{7.20}$$ We know define a collection of balls $B_\sigma$, indexed by $\sigma \color{blue}{\in} \{ 0 , 1 \}^n$, centered at points of $\{ x_1 , x_2 , \ldots \}$ as follows: Set $B_\varnothing$ to be the ball of radius $\frac{1}{2}$ about $x_1$. If $B_\sigma$ is defined for all $\sigma \color{blue}{\in} \{ 0 , 1 \}^n$, and $\tilde{x}_\sigma$ are their centers, let $r_n$ be the minimum of the distance between $f_0 ( \tilde{x}_\sigma )$ and $f_1 ( \tilde{x}_\sigma )$ for all $\sigma \in \{ 0 , 1 \}^n$. Then let $B_{\sigma0}$ be the ball centered at $f_0 ( \tilde{x}_\sigma )$ of radius $\frac{r_n}{4}$, and similarly let $B_{\sigma 1}$ be the corresponding ball centered at $f_1 ( \tilde{x}_\sigma )$. These balls are disjoint with $B_{\sigma 0} , B_{\sigma 1} \subset B_\sigma$ and, by induction, the same is true for $\{ B_\sigma : \sigma \color{blue}{\in} \{ 0 , 1 \}^n \}$ for all $n \geq 1$.

One very large problem with this proof is that for each $x_k$ we have chosen the two points which would follow it in the construction of the tree before knowing how far apart they should be. We know that $0 < d ( f_i ( x_k ) , x_k ) \leq 2^{-k}$, however the stage at which $x_k$ has been chosen to be a $\tilde{x}_\sigma$ the radius of the corresponding ball $B_\sigma$ might already be so small that it does not contain $f_i ( x_k )$, making the assertion that $B_{\sigma i} \subset B_\sigma$ false! I do not see a way of fixing the proof as written, as in general it is a bad thing to choose objects before necessary (and my outline/proof in the other answer avoids choices until the necessity of that choice has been made absolutely clear!).

A more minor point is that inductive hypotheses should be given at some point in this inductive construction. In order to show that $B_{\rho i}$ and $B_{\sigma j}$ are disjoint for $\rho , \sigma \in \{ 0 , 1 \}^n$ and $i,j \in \{ 0 , 1 \}$ we at the very least need to assume that $B_\sigma \cap B_\rho = \emptyset$. This failing is easier to fix, but the fact that it was not doesn't give me a warm, fuzzy feeling inside.