# Uncountable Sets [closed]

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.

-

## closed as too localized by Andrey Rekalo, Akhil Mathew, Robin Chapman, François G. Dorais♦Aug 8 '10 at 14:21

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

Please see the faq for suggestions of sites where this question is more appropriate - mathoverflow.net/faq#whatnot –  François G. Dorais Aug 8 '10 at 14:22

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$.

-

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.

-
As in one of the other threads here, maybe it would be better to cast it in DIRECT form like this: If $f \colon \mathbb{N} \to \mathbb{R}$, then there is some real number not in the range of $f$ –  Gerald Edgar Aug 8 '10 at 17:00