MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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 - – François G. Dorais Aug 8 '10 at 14:22
up vote 2 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer
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

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