Uncountability of the reals through nested intervals

March 22, 2020

From Ebbinghaus, Flum, and Thomas' Mathematical Logic, chapter 2, exercise 1.3:

Let α:NR\alpha : \mathbb{N} \to \mathbb{R} be given. For a,bRa, b \in \mathbb{R} such that a<ba < b show that there is a point cc in the closed interval I=[a,b]I = [a,b] such that c{α(n):nN}c \notin \{\alpha(n) : n \in \mathbb{N}\}. Conclude from this that II, and hence R\mathbb{R} also, are uncountable. (Hint: By induction define a sequence I=I0I1I = I_0 \supset I_1 \supset \dots of closed intervals such that α(n)In+1\alpha(n) \notin I_{n+1} and use the fact that nNIn\bigcap_{n \in \mathbb{N}} I_n \ne \varnothing.)

Define I0=[a,b]I_0 = [a,b]. For any n0n \geq 0, if In=[an,bn]I_n = [a_n, b_n], let m=an+bn2m = \frac{a_n+b_n}{2} and define

In+1={[an,m]if α(n)>m[m,bn]if α(n)<m[an,an+m2]if α(n)=mI_{n+1} = \begin{cases} [a_n, m] & \text{if } \alpha(n) > m \\ [m, b_n] & \text{if } \alpha(n) < m \\ [a_n, \frac{a_n+m}{2}] & \text{if } \alpha(n) = m \\ \end{cases}

For any n0n \geq 0, we can see that for any value of α(n)\alpha(n), we have α(n)In+1\alpha(n) \notin I_{n+1}, so α(n)kNIk\alpha(n) \notin \bigcap_{k\in\mathbb{N}} I_k Therefore, if cnNInc \in \bigcap_{n\in\mathbb{N}} I_n, then cα(n)c \neq \alpha(n) for any nNn \in \mathbb{N}.

As nNIn\bigcap_{n\in\mathbb{N}} I_n \neq \varnothing there is some cnNInc \in \bigcap_{n\in\mathbb{N}} I_n, and for this cc, we have cI0=[a,b]c \in I_0=[a,b] (and cRc \in \mathbb{R}) and cα(n)c \neq \alpha(n) for any nNn \in \mathbb{N}, so for any given α\alpha, then α\alpha is not surjective onto [a,b][a,b] (and R\mathbb{R}). Therefore, [a,b][a,b] (and R\mathbb{R}) is not countable.