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

Question

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,

Answer 1

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

Answer 2

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

Answer 3

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.