Question

I've read that the set of real numbers R is uncountable. It was proved by contradiction. A number x that is not in the f(n) side was constructed. Ultimately it was said that "x is not f(n) for any n because it differs from f(n) in the nth fractional digit. I can't understand the last part. I understand what is being said but don't see how it proves that R is uncountable.

Answer 1

Assume the interval $[0,1)$ is countable. Then we can write down all numbers like that:

• $a_0 = 0.a_{0,0}a_{0,1}a_{0,2}\dots$
• $a_1 = 0.a_{1,0}a_{1,1}a_{1,2}\dots$
• $a_2 = 0.a_{2,0}a_{2,1}a_{2,2}\dots$
• $\dots$

Now we construct a new number $b=0.b_0b_1b_2\dots$ in the following way. We look at $a_{ii}$. If this digit is $1$, then $b_i=2$, otherwise we set $b_i=1$. Therefore we constructed a now number, that is not in our list of $a_i$, since it differs from each number in one position. But the number $b$ is clearly in the interval $[0,1)$ and we assumed, that we have written down all numbers. Contradiction, i.e., the set was not countable.

And since $[0,1) \subseteq \mathbb{R}$, the real numbers are also not countable.

Edit. Using the notation of the original posting: $b=x$ and $f(n)=a_n$.

Answer 2

It is an indirect proof starting with the assumption that, contrary to the statement of the theorem, there does exist a surjection $f:\{0,1,\dots\}\to R$ of the natural numbers onto the reals. Given $f$, with clever manipulations, we exhibit a real number that is not equal to any value $f(n)$, and so $f$ is not onto the reals a contradiction. In indirect proofs, reaching a contradition is fine, as that shows the impossiblity of the negation of the statement.