Proof that a perfect set is uncountable
There is something I don't understand about the proof that perfect sets are uncountable. The same proof is present in Rudin's Principles of Mathematical Analysis.
Do we assume that our construction of $U_n$ must contain all points of $S$? What if we are only collecting evenly-indexed points of $S$ ($x_{2n}$)? We would still get an infinitely countable subset of $S$, and the rest of $S$ can be used to provide points for $V$. What am I missing?
Solution 1:
$\newcommand{\cl}{\operatorname{cl}}$ The result at the cited link can be strengthened: a perfect subset of $\Bbb R$ (or indeed of any complete metric space) has cardinality at least $2^\omega$ and therefore is certainly uncountable. The proof uses the same basic idea in a slightly more sophisticated way.
Proof. Let $\langle X,d\rangle$ be a complete metric space, and let $S$ be a perfect subset of $X$. Let $\Sigma$ be the set of finite sequences of $0$’s and $1$’s, and for each $n\in\Bbb N$ let $\Sigma_n=\{\sigma\in\Sigma:|\sigma|=n\}$. If $\sigma\in\Sigma$ and $i\in\{0,1\}$, denote by $\sigma^{\frown}i$ the sequence obtained by appending $i$ to $\sigma$; thus, if $\sigma\in\Sigma_n$, then $\sigma^{\frown}i\in\Sigma_{n+1}$. For $\sigma,\tau\in\Sigma$ write $\sigma\prec\tau$ iff $\sigma$ is a proper initial segment of $\tau$. I’ll construct open sets $U_\sigma$ for $\sigma\in\Sigma$ in such a way that:
- $U_\sigma\cap S\ne\varnothing$ for each $\sigma\in\Sigma$,
- $\{U_\sigma:\sigma\in\Sigma_n\}$ is pairwise disjoint for each $n\in\Bbb N$,
- $\cl U_\sigma\subseteq U_\tau$ whenever $\sigma\prec\tau$, and
- $\operatorname{diam}U_\sigma\le 2^{-n}$ whenever $\sigma\in\Sigma_n$.
Suppose that this has been done. Let $\Sigma_\omega$ be the set of infinite sequences of $0$’s and $1$’s, and note that $|\Sigma_\omega|=2^\omega$. For each $\sigma\in\Sigma_\omega$ and $n\in\Bbb N$ let $\sigma^n\in\Sigma_n$ be the initial segment of $\sigma$ of length $n$, and let $$F_\sigma=\bigcap_{n\in\Bbb N}\left(S\cap\cl U_{\sigma^n}\right)\;;$$ conditions (1), (3) and (4) and the completeness of $X$ ensure that $F_\sigma=\{x_\sigma\}$ for some $x_\sigma\in X$, and condition (2) ensures that if $\tau\in\Sigma_\omega$ is distinct from $\sigma$, then $F_\tau\cap F_\sigma=\varnothing$ and hence $x_\tau\ne x_\sigma$. Thus, $\{x_\sigma:\sigma\in\Sigma_\omega\}$ is a subset of $S$ of cardinality $2^\omega$.
To construct the sets $U_\sigma$, let $y_\varnothing\in S$ be arbitrary, and let $U_\varnothing=B(y_0,1)$; $y_0$ is an accumulation point of $S$, so $S\cap U_\varnothing$ is infinite. (Here $\varnothing$ is the sequence of length $0$.) Given $U_\sigma$ for some $\sigma\in\Sigma_n$ such that $S\cap U_\sigma$ is infinite, let $y_{\sigma^{\frown}0}$ and $y_{\sigma^{\frown}1}$ be distinct points of $S\cap U_\sigma$. There is a positive $r\le 2^{-(n+1)}$ such that $B(y_{\sigma^{\frown}0},r)\cap B(y_{\sigma^{\frown}1},r)=\varnothing$, and we set $U_{\sigma^{\frown}i}=B(y_{\sigma^{\frown}i},r)$ for $i\in\{0,1\}$. The points $y_{\sigma^{\frown}i}$ are accumulation points of $S$, so the sets $S\cap U_{\sigma^{\frown}i}$ are infinite, and the recursive construction goes through.
Solution 2:
There is an alternative proof, using what is a consequence of Baire's Theorem:
THM Let $(M,d)$ be a complete metric space with no isolated points. Then $(M,d)$ is uncountable.
PROOF Assume $M$ is countable, and let $\{x_1,x_2,x_3,\dots\}$ be an enumeration of $M$. Since each singleton is closed, each $X_i=X\smallsetminus \{x_i\}$ is open for each $i$. Moreover, each of them is dense, since each point is an accumulation point of $X$. By Baire's Theorem, $\displaystyle\bigcap_{i\in\Bbb N} X_i$ must be dense, hence nonempty, but it is readily seen it is empty, which is absurd. $\blacktriangle$.
COROLLARY Let $(M,d)$ be complete, $P$ a perfect subset of $M$. Then $P$ is uncountable.
PROOF $(P,d\mid_P)$ is a complete metric space with no isolated points.
ADD It might be interesting to note that one can prove Baire's Theorem using a construction completely analogous to the proof suggested in the post.
THM Let $(X,d)$ be complete, and let $\langle G_n\rangle$ be a sequence of open dense sets in $X$. Then $G=\displaystyle \bigcap_{n\in\Bbb N}G_n$ is dense.
PROOOF We can construct a sequence $\langle F_n\rangle$ of closed sets as follows. Let $x\in X$, and take $\epsilon >0$, set $B=B(x,\epsilon)$. Since $G_1$ is dense, there exists $x_1\in B\cap G_1$. Since both $B$ and $G_1$ are open, there exists a ball $B_1=B(x_1,r_1)$ such that $$\overline{B_1}\subseteq B\cap G_1$$
Since $G_2$ is open and dense, there is $x_2\in B_1\cap G_2$ and again an open ball $B_2=B(x_2,r_2)$ such that $\overline{B_2}\subseteq B_1\cap G_2$, but we ask now that $r_2\leq r_1/2$. We then successively take $r_{n+1}<\frac{r_n}2$. Inductively, we see we can construct a sequence of closed bounded sets $F_n=\overline{B_n}$ such that $$F_{n+1}\subseteq F_n\\ \operatorname{diam}D_n\to 0$$
Since $X$ is complete, there exists $\alpha\in \displaystyle\bigcap_{n\in\Bbb N}F_n$. But, by construction, we see that $\displaystyle\alpha\in \bigcap_{n\in\Bbb N}G_n\cap B(x,\epsilon)$
Thus $G$ is dense in $X$.$\blacktriangle.$
Solution 3:
The crux of the argument is that we make sure to collect all the points. List the elements $\{x_{1}, x_{2}, \cdots , x_{n}, \cdots\}$ and then take the open interval $U_1$. If $x_{2}$ is not in $U_{1}$, ignore it, as it will not show up in $V$. If $x_{2}$ is in $U_{1}$, we construct $U_{2}$. In this way, we go down the list of $x_{n}$, and we ignore them if they are not in current $U_{j}$ we are considering, and otherwise we construct $U_{j+1}$. When we build $V$, and prove it is nonempty, we have shown that we have either actively eliminated points or ignored those that could not have ended up in $V$. Thus we get a contradiction.