Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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? –  Babak S. 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

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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