This question already has an answer here:

I cannot seem to understand the proof of why the interval $\left ( 0,1 \right )$ is not countable.

The proof that is written in my book using the method of Reductio ad absurdum.

It starts with the following statement:

We know that every real number can be written as a decimal.

Let $x_{1} = 0,x_{11}x_{12}x_{13}...$

$x_{2} = 0,x_{21}x_{22}x_{23}...$

$x_{3} = 0,x_{31}x_{32}x_{33}...$

Then by using the diagonial argument it constructs a $y = 0,y_{i}...$ but cannot understand the process that follows.


marked as duplicate by Asaf Karagila, Hanul Jeon, Lord_Farin, MathOverview, Dan Rust Nov 11 '13 at 12:22

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ The point here is that the supposed list $x_1$, $x_2$, ... is <i>assumes</i> to be countable. The diagonal argument constructs $y$ which is different from every $x_i$, and thus not in the list. So the interval cannot be countable. $\endgroup$ – Jas Ter Nov 11 '13 at 11:11
  • $\begingroup$ Can you elaborate a little more o nthe diagonal argument please? $\endgroup$ – Rrjrjtlokrthjji Nov 11 '13 at 11:21
  • $\begingroup$ If it's countable, its Lebesgue measure must be $0$. This is absurd because its measure is $1$. $\endgroup$ – Makoto Kato Nov 11 '13 at 11:27
  • $\begingroup$ Sorry but I have no idea what a Lebesgue measure is... I am a first year student. $\endgroup$ – Rrjrjtlokrthjji Nov 11 '13 at 11:31
  • $\begingroup$ @Nick : This argument is called "Cantor's diagonalization". Google that and you should find plenty of information. $\endgroup$ – Prahlad Vaidyanathan Nov 11 '13 at 11:32

For each $x_{ii}$, you pick $y_i$ such that $x_{ii}\neq y_i$, and of course, $y_i$ can only take values from $0,1,2,3,4,5,6,7,8,9$.

Then you set $y=0,y_1y_2y_3\dots$, and you'll note that $x_i\neq y$ for all $x_i$. So there is no bijection between $(0,1)$ and $\mathbb N$.

But of course this argument doesn't quite work, because what happens if $x_1=0.500\dots$, and $y_1=4$, $y_i=9$ for all $i\geq 2$. Then I would get $y=0.4999\dots=0.5=x_1$. So to fix this, simply don't let $y_i$ take the values $0$ or $9$. That's because a number has two decimal representations if and only if its decimal representation has repeating $9$ or repeating $0$ after some point.


(Then by using the diagonial argument it constructs a y=0,yi... )

It constructs a number that is different from all the previous numbers you constructed. Thus you found something that exceeds the countability of the set you have already formed. That's why we call it uncountable.

  • $\begingroup$ Thanks for the answer, fellow countryman! $\endgroup$ – Rrjrjtlokrthjji Nov 11 '13 at 11:28
  • $\begingroup$ @Nick haha,nice $\endgroup$ – Haha Nov 11 '13 at 11:31

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