Ok so, I was given given a proof of this by my lecturer, but I'm not understanding it fully,, and I was wondering if this suffices as a proof.

It is enough to show that $(0,1)$ is uncountable.
Let $x \in (0,1)$ and write $x$ in it's decimal expansion. i.e. $x= 0.a_1a_2a_3...$, for $a_i \in \{0,1,2....9\}$ for $i \in \Bbb N$
Next assume that $(0,1)$ is countable, that is $(0,1) =\{x_1, x_2, x_3,... \}$. We write
$x_1 = 0.a_{11}a_{12}a_{13}...$
$x_2 = 0.a_{21}a_{22}a_{23}...$

This is where I differ from my lecturer. He says:
let $y= b_1b_2b_3...$, where
$b_i = 2$ if $a_{ii} \neq 2$ and
$b_i = 3$ if $a_{ii} = 2$ for $i \in \Bbb N$
Then $y \in (0,1)$, but $y \neq x_i$, for all $i \in \Bbb N$
This contradiction proves that $(0,1)$ is uncountable.

What I'm saying is:
Let $b_i = a_{ii} + 1$.
Then $y$ will differ from $x_1$ in the first decimal position, from $x_2$ in the second decimal position,... and from $x_n$ in the the $n^{th}$ decimal position. Hence, the list $\{ x_1, x_2,... \}$ can never be an exhaustive list and so $(0,1)$ is uncountable.

Just want to know what you think. Thanks.

  • 1
    $\begingroup$ What happens when $a_{ii} = 9$? Though, in general, the proof could just say $b_i \neq a_{ii}$. $\endgroup$ – Karolis Juodelė May 28 '14 at 15:40
  • $\begingroup$ @KarolisJuodelė Ok, so if I say that then, the proof is acceptable? $\endgroup$ – Crockett May 28 '14 at 15:42
  • $\begingroup$ $\Bbb R$ is a complete metric space, hence uncountable by Baire's theorem. $\endgroup$ – Pedro Tamaroff May 28 '14 at 16:40

Your proof doesn't work in case $a_{ii} = 9$. Perhaps you could include $b_i = 0$ if $a_{ii} = 9$.

The reason the instructor used $2$ and $3$ is to avoid the problem of having an infinite string of $9$'s.

To guarantee that each $x$ has a unique representation, you can require that each sequence $\{a_{ij}\}$ does not end in an infinite string of $9$'s. If it did, you could represent the number $x$ with a finite decimal representation. The problem is that the number you construct using the $b_i$ could end in an infinite string of $9$'s which will have a different representation from every other number in the list, but could in fact equal one of those numbers. For instance, you might construct $0.4999999\ldots$ which already appeared in the list as $0.5000000\ldots$. Avoiding $9$'s altogether circumvents this problem.


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.