# 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?

-

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.

-
Ahh, right. If $x_{i+1}$ is not in $U_i$, it cannot show up in $V$. Thank you! –  PeterM Sep 25 '12 at 1:02

$\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:

1. $U_\sigma\cap S\ne\varnothing$ for each $\sigma\in\Sigma$,
2. $\{U_\sigma:\sigma\in\Sigma_n\}$ is pairwise disjoint for each $n\in\Bbb N$,
3. $\cl U_\sigma\subseteq U_\tau$ whenever $\sigma\prec\tau$, and
4. $\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.

-
Pardon the ignorance, but then any metric space $(X,d)$ that proves to be complete satisfies $|X|>\omega$? Or can we build a not necessarily uncountable complete metric space that has no perfect subsets? –  Pedro Tamaroff Apr 6 '13 at 0:18
Minor correction: You start with $y_\varnothing$ but then swap to $y_0$. –  Pedro Tamaroff Apr 6 '13 at 0:36
What is $F$ in the definition of $F_\sigma$? Should it be $S$? –  Pedro Tamaroff Apr 6 '13 at 0:41
@Peter: It should indeed; bad fingers. –  Brian M. Scott Apr 6 '13 at 3:05
@tomasz: Yes, I just constructed a subset of power $2^\omega$. I don’t remember after all this time, but I suspect that when I wrote the answer, I added the parenthetical comment about complete metric spaces after I’d done everything else and didn’t think about the fact that that increased the possible cardinality. –  Brian M. Scott May 31 '13 at 21:56

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.$

-
This is a nice proof, but you lose the information that you gain otherwise. You can just tell that the space is uncountable, and not that it has to be at least of size $2^{\aleph_0}$. –  Asaf Karagila May 31 '13 at 18:19
@AsafKaragila So as not to make this a long comment thread, could you drop by the chat to explain? Please =) –  Pedro Tamaroff May 31 '13 at 18:20
Of course not. But to keep things simple, your proof is of course correct, but the only thing you can prove is that the space is not countable. Suppose that $2^{\aleph_0}=\aleph_2$. We can't use this proof to decide whether a perfect set (say, of real numbers) has cardinality $\aleph_1$ or $\aleph_2$ -- because we can only conclude that it is uncountable. In Brian's answer on this thread he shows that in fact we can prove more. We can prove that a perfect set must have cardinality $\geq2^{\aleph_0}$, not just $>\aleph_0$. –  Asaf Karagila May 31 '13 at 18:23
@AsafKaragila I see, but I am not even close to yours or Brian's knowledge, so I cannot aim for that. This is my grain of salt. I guess my answer is more accessible in some way, and Brian's is much better. Of course, that's the price we have to pay. –  Pedro Tamaroff May 31 '13 at 18:27
Oh, I do agree that this is a very good answer and an excellent use of Baire's category theorem. It's just... a crude answer, compared to a slightly more refined result that one can achieve. –  Asaf Karagila May 31 '13 at 18:30