# Proof $\{x \in \mathbb{R} \mid 0 \leq x \leq 1\}$ in uncountable

Prove that the interval $\{x \in \mathbb{R} \mid 0 \leq x \leq 1\}$ in uncountable. In other words show that no function $f\colon \mathbb{N} \to [0,1]$ can have one to one and onto correspondence.

For convenience, define $a_0 = 0$ and $b_0 = 1$

Define a midpoint of each interval to be $mn = \frac{(an + bn)}{2}$, so that $m_0 = \frac{1}{2}$

Then for $n\leq 1$:

if $f(n) \geq mn-1$, then $an = \frac{(an-1 + mn-1)}{2} \text{and }bn = bn-1$

if $f(n) < m$, then $an = an-1$, $bn = \frac{(mn-1 + bn-1)}{2}$

So, in other words, always take the right fourth or the left fourth of the interval to get the next interval, whatever it takes to "avoid" $f(n)$.

I really don't like the route I am taking. Can you perhaps guide me?

• use cantor diagonalization – user58512 Jan 24 '13 at 7:49
• Why don't you show that it has the same cardinal as $\Bbb R$ directly? – mrs Jan 24 '13 at 7:53
• This looks like its going somewhat in the direction of Cantor's first proof of uncountability. – Hagen von Eitzen Jan 24 '13 at 7:58
• Yes but unsuccessfully. I may just try using the Cantor Diagonalization. Gonna do a little research – math101 Jan 24 '13 at 8:02

Here are two ideas (for guidance, but if it doesn't help I will give the full details later):

First idea: if you "know" that $\mathbb R$ is uncountable: there is a bijection between $\mathbb R$ and $(0,1)$. In fact, there is an order-preserving bijection. Then, once you have established that $(0,1)$ is uncountable, uncountability of $[0,1]$ follows.

Second idea: Assume on the contrary that you can enumerate all elements in $(0,1)$. To make your life easier, write $x=0.x_1x_2 \dots$, in base $2$ so that $x_i \in \{0,1\}$. Then write them one below the other, starting with $(0,0,0, \dots)$ and numbering the rows:

$0:(0,0,0,0, \dots )$

$1:(1,0,0,0, \dots )$

$2:(1,1,0,0, \dots )$

$3:(1,1,1,0, \dots )$

$\vdots$

and so on. If $n$ denotes the row number and $k$ denotes the position in the sequence of $0$s and $1$s, consider the sequence consisting of the digits $n=k$ (the diagonal). Let's denote it by $d = d_0d_1d_2 \dots$. Then think about $d$ with all digits inverted.