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?

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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.