Definition of a countable set, from Stanford, as I didn't want to quote Wikipedia:
Definition. A set S is countable if |S| = |N|.
Thus a set S is countable if there is a one-to-one mapping of Num onto S, that is, if S is the range of an infinite one-to-one sequence.
So it seems that if we can define a set of numbers that does not map one-to-one to the natural numbers, then it is not a countable set. The natural numbers quite obviously map one-to-one to the natural numbers, so can they possibly be uncountable?
Let's say we have a list containing all of the natural numbers. Excerpt:
…
000099
000100
000101
000102
…
We can define a number that is different from each element in this list as follows: for the ith number in the list, the ith digit is one of the 8 (or 9) non-zero alternatives that make our new number different from the number on the list. For example:
…
00009 9
0001 0 0
000 1 01
00 0 102
…12 3456
As we keep going, we will end up with a sequence of non-zero digits, which forms a valid Natural number, that is not on our list of all natural numbers, so our mapping of the natural numbers to the natural numbers breaks.
Does this make sense, or is there something I'm missing?
Best Answer
Your error is in the assertion:
Natural numbers have only finitely many nonzero digits in their decimal expansion. This can be proven by induction: it is true of $1$; and the number of nonzero digits in the decimal expansion of $n+1$ is at most one more than that of $n$ (you need at most one more digit before you start padding with $0$s on the left).
An infinite list which contains infinitely many nonzero digits does not yield a natural number. In fact, one can prove that your procedure will produce a sequence of digits with infinitely many nonzero digits, hence not correspond to a natural number.
Let's say that your procedure selects $0$ whenever possible (that is, whenever the $i$th digit, from right to left, of the $i$th natural number, is nonzero; you really want this, because if you insist, as in your post, that you always select a nonzero digit, then you guarantee what you get is not a natural number). Can the list be arranged in such a way that the $i$th digit of the $i$th number is nonzero for all $i\gt N$ for some $N$? No: for any given $N$, there are $10^{N-1}$ natural numbers that require fewer than $N$ digits to write; since there are only $N$ positions prior to $N$, at least one of these $10^{N-1}$ numbers must be listed in a position below $N$; but if it is listed in position $j\gt N$, then its $j$th digit will be $0$, so the constructed sequence will necessarily have a nonzero entry at $j\gt N$. Since this holds for all $N$, the list obtained is never eventually $0$, and so does not correspond to a natural number.
Now, if you want to extend your notion of numbers to include expressions with infinitely many nonzero digits, then your argument is correct: the set of all such "numbers" is not countable. However, those are not the natural numbers.