# What is wrong with this proof of the countability of the reals?

By using the following lemmas:

1. A countable union of countable sets is countable.

2. Cartesian products of integers are countable.

Wouldn't it be possible to prove the countability of the reals between 0 and 1, by partitioning them into countable sets each one uniquely identified by a Cartesian pair (m, n)?

Each set (m, n) contains all reals that have their first m digits sum equal to n and all their other digits zero.

By the second lemma above there is a countable such (m,n) that cover the interval [1,0]. And each such set is also countable since it contains a finite amount of numbers. Therefore by using the first lemma above wouldn't that prove that the the reals between 1 and 0 are countable?

Appreciate any feedback on the above on where I went wrong; I suspect it might be in how I used the second lemma to encode the above sets and show there is countable number of such sets.

many thanks,

-
When do you count the real numbers whose decimal expansion has no zeros, say, $\frac{1}{9}$? –  Zhen Lin Jun 24 '12 at 10:49
Since $\mathbb{R}$ in uncountable, the answer must be negative :-). I suspect that arbitrary cartesian products of countable sets need not be countable... –  Siminore Jun 24 '12 at 10:50
And each such set is also countable since it contains a finite amount of numbers... Why is that so? The set of reals that have the first m digits that sum up to n is certainly not finite (and is in fact uncountable). –  Did Jun 24 '12 at 10:50
Thank you for the comments, I have modified the third paragraph again. I hope this is not bad etiquette here. Also, I don't have any doubts that the proof is wrong, just trying to figure out how. –  user34381 Jun 24 '12 at 11:07
You have not addressed Asaf's objection: the subset of real numbers described in the third paragraph is only those whose decimal expansion ends in a string of infinitely many zeros. That leaves out a lot of real numbers. –  Lee Mosher Jun 24 '12 at 16:10

This is false, as remarked by others.

Suppose that $0.d_1d_2\ldots d_k$ is in $(m,n)$ then any real number which has the same $k$ digits would be in $(m,n)$. There are uncountably many ways to produce such numbers.

For example, any number whose first digit is $1$ is going to be in $(1,1)$, so for any number $x\in [0,1]$ we have that $0.1+\frac{x}{10}\in(1,1)$. That is uncountably many, right there.

To the edit:

Now you only cover a subset of the rationals, and so this is really just a countable result. For example $\frac1{\sqrt 2}$ is not in any of the $(n,m)$.

-
Here's another one you missed in the edited method: $\frac{1}{3}=.33333333333....$ –  Lee Mosher Jun 24 '12 at 13:40

Let's apply the argument to something simpler: Sequences of $0$s and $1$s. There are uncountably many such sequences and the diagonal argument is actually easier in this case, since one doesn't have to worry about non-unique representations of reals.

In your set, you control only the first $m$ terms, but you can take any finite sequence, and since there are uncountably many sequences of $0$s and $1$s, there are uncountably many ways to extend the finite sequence.

If you cut all the sequences off by eventually requiring them to be zero forevery, you cut out an uncountable number of ways to extend a finite sequence. What you get is countable, but doesn't cover all such sequences.

-

Im not convinced of the finiteness of the set corresponding to $(m,n)$. There are infinitely many real numbers with first decimal digit being $1$. So the set coresponding to $(1,1)$ is infinite (and actually equal in cardinality to the real numbers).

-