Bijection between closed uncountable subset of $\Bbb R$ and $\Bbb R$.

This is probably a really stupid question but I'm hoping it's true: can we find a bijection between any uncountable closed subset of $\Bbb R$ and $\Bbb R$ (real number line)?

Solution 1:

This is a nice result due to Cantor that is good to understand well. Let me expand André Nicolas's answer.

We need a modicum of set theory, specifically, a working understanding of $\omega_1$, the first uncountable ordinal.

1.

First, we need the Cantor-Baire stationary principle: Suppose that to each countable ordinal $\alpha$ we assign a closed set $E_\alpha\subseteq\mathbb R$ in such a way that $E_\alpha\supseteq E_\beta$ whenever $\alpha<\beta$. There must then exist a countable ordinal $\alpha_0$ such that for all $\alpha>\alpha_0$, $E_\alpha=E_{\alpha_0}$.

The idea of the proof of this result is actually simple (for details, Kechris's book on Classical descriptive set theory is an excellent reference): If $E_\alpha\supsetneq E_{\alpha+1}$, there is an open interval $I_\alpha$ with rational endpoints that meets $E_\alpha$ but not $E_{\alpha+1}$. Using that the sets are decreasing, we can in fact assign different intervals to different ordinals. This gives us what we want, since there are only countably many open intervals with rational endpoints.

This principle is applied in a variety of places in analysis. For example, in the theory of the Denjoy integral (though modern presentations use the Henstock–Kurzweil approach). The other typical application is to develop the basic results connected with the Cantor-Bendixson derivative, which is what we need now.

2.

The (Cantor-Bendixson) derivative $E'$ of a set $E\subseteq\mathbb R$ is the set of limit points of $E$. Since $E$ and its closure have the same limit points, we may as well assume that $E=E_0$ is closed. We can now form a decreasing sequence of closed sets $E_0\supseteq E_1\supseteq\dots\supseteq E_\alpha\supseteq\dots$ indexed with the countable ordinals, by letting $E_{\alpha+1}=E_\alpha'$, and taking intersections of the sets obtained so far at limit stages.

By the Cantor-Baire stationary principle, we must reach a stage $\alpha$ such that $E_\alpha'=E_\alpha$. This means that either $E_\alpha$ is a (non-empty) perfect set, or else $E_\alpha$ is empty.

Now, for any $E$, if $x\in E\setminus E'$, then $x$ is an isolated point of $E$, so $E\setminus E'$ is necessarily countable. This means that any closed set can be written as the union of a countable set (namely, the union of the isolated points of the $E_\beta$ for $\beta<\alpha$) and a set that is either empty or perfect (namely, $E_\alpha$).

The outcome of this argument is that if a closed set is uncountable, then it necessarily contains a perfect subset.

3.

The conclusion we seek is now reached by arguing that any perfect set contains a copy of the Cantor set $C$. Since $|C|=2^{\aleph_0}=|\mathbb R|$, this gives us the result that any uncountable closed set has the same size as $\mathbb R$.

To prove this, we use a recursive construction: Suppose $A$ is perfect, so it has at least two points $p_0$ and $p_1$. Let $r=|p_1-p_0|$ be the distance between $p_0$ and $p_1$ We can find small intervals $I_0$ and $I_1$ with disjoint closures that contain $p_0$ and $p_1$, respectively. Since $A$ is perfect, $A\cap I_0$ must contain at least two other points $p_{00}$ and $p_{01}$, both at distance at most $r/2$ from $p_0$, and similarly, $A\cap I_1$ must contain distinct points $p_{10}$ and $p{11}$ at distance at most $r/2$ of $p_1$. We can find intervals with pairwise disjoint closure, $I_{00},I_{01}\subset I_0$ containing $p_{00},p_{01}$, respectively, and similarly for $I_1$. Continuing this way, we produce points $p_s$ in $A$ for each finite sequence $s$ of $0$s and $1$s in such a way that for each infinite sequence $x=(x(0),x(1),\dots)$, the sequence $p_{x(0)},p_{x(0)x(1)},p_{x(0)x(1)x(2)},\dots$ converges. Call $p_x$ its limit. One easily checks that the points $p_x$ are all distinct, and all belong to $A$.

4.

This gives the result. Let me mention an extension. A set is Borel if it can be obtained by starting with the open intervals, and closing under the operations of countable union and complementation. A set is analytic if it is the continuous image of a Borel set.

First, one can easily check that, as long as we start with a Polish space in place of $\mathbb R$, the sketch above goes through, so any closed subset of a Polish space is either countable or of the same size as $\mathbb R$. (Recall that $X$ is Polish iff it is a completely metrizable separable space.)

Second, one can check, though this takes some work, that any analytic set is the injective image of a closed subset of the Polish space $\mathbb N^{\mathbb N}$. This means that the result holds not just for closed sets, but in fact for analytic sets: Any such set is either countable, or of the same size as $\mathbb R$.

As André pointed out, one of the early suggested approaches to the continuum problem was to argue by some sort of induction on the topological complexity of the sets of reals that they are countable or of size $|\mathbb R|$. The first step is to see this for open and closed sets, and this was done by Cantor. Early results in descriptive set theory extended this effort to include all analytic sets, by the method just indicated. Further extensions (going well beyond any sets that ever show up in analysis) had to wait until the late part of the twentieth century, and require large cardinals. Of course, now we know that "arbitrary" sets of reals do not need to have this perfect set property, but the descriptive set theoretic work I'm indicating shows that any sets without the property are in essence pathological.

Solution 2:

This is true. It is a consequence of theorems of 1) Cantor/Bendixson and 2) Cantor.

1.) Every closed subset of $\mathbb{R}$ is the union of an at most countably infinite set and a perfect set.

2.) A non-empty perfect subset of $\mathbb{R}$ has cardinality $c$.

Remark: This result was part of Cantor's search for a proof of the Continuum hypothesis. Related questions are still an active area of research.

Solution 3:

Here is a proof that does not use any transfinite induction at all!

Take any uncountable closed subset $S$ of $\mathbb{R}$.

Let $S_n = S \cap [n,n+1]$ for each integer $n$.

Then $S_n$ is uncountable for some integer $n$, so we can assume that $S \subseteq [a,b]$ for some reals $a,b$.

Let $p = \sup \{ x : x \in [a,b] \land \text{$S \cap [a,x)$ is countable} \}$, which exists because $S \cap [a,a)$ is countable.

Then $S \cap [a,p) = \bigcup_{n=1}^\infty S \cap [a,p-\frac1n)$ is countable.

Similarly let $q = \inf \{ x : x \in [a,b] \land \text{$S \cap (x,b]$ is countable} \}$.

Then $S \cap (q,b]$ is likewise countable.

Clearly $p < q$, otherwise $S$ would be countable.

Let $r = \frac12(p+q)$. Then $S \cap [a,r]$ and $S \cap [r,b]$ are both uncountable, by definition of $p$ and $q$.

Thus $S \cap [p,r]$ and $S \cap [r,q]$ are uncountable closed subsets of $[p,q]$, and $r-p = q-r < \frac12(b-a)$.

Therefore we can iterate this process starting from $[0,1]$. Let $T$ be the binary tree with root $[0,1]$ where each node $[a,b]$ has children $[p,r]$ and $[r,q]$ with length at most half their parent's, such that $S \cap [p,r]$ and $S \cap [r,q]$ are uncountable.

For every downward path $P$ in $T$:

  $P$ is a sequence of nested closed intervals with length decreasing to zero.

  Let $c$ be the unique point in their intersection.

  If $c \notin S$:

    Let $u = \inf \{ x : x \in [0,c] \land S \cap [x,c] = \varnothing \}$.

    Let $v = \sup \{ x : x \in [c,1] \land S \cap [c,x] = \varnothing \}$.

    Then $c \in (u,v)$ and $S \cap (u,v) = \varnothing$.

    But eventually the interval along $P$ will have length less than $\min(c-u,v-c)$.

    Thus some interval $I$ in $P$ is contained in $(u,v)$, contradicting $S \cap P$ being uncountable.

  Therefore $c \in S$.

  Also $c$ is different for any downward path in $T$ that is different from $P$.

Therefore $S$ has at least as many elements as there are countably infinite binary sequences.

Thus the reals inject into $S$, and hence there is a bijection from $S$ to the reals.

As pointed out by Andrés E. Caicedo in the comments, my initial comment was false, because this proof uses countable choice twice, via the theorem that a countable union of countable sets is also countable.