Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
"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." That makes no sense at all. The set $\{1,2,5\}$ is a set that does not map one-to-one to the natural numbers. You're saying that somehow means something about countability of the set of all natural numbers? –  Michael Hardy Feb 7 '12 at 4:58
    
@Michael: The source uses "countable" to mean "countably infinite" (what I used to call "denumerable" as an undergrad), and "at most countable" to mean "finite or countably infinite". But really, that whole thing is a preface to what is often a way to "show" that the diagonal argument cannot be true because then it would "show" the naturals are uncountable... –  Arturo Magidin Feb 7 '12 at 5:29
2  
Well, at least your proof is correct to show that $p$-adic integers are uncountable. –  FelixCQ Feb 7 '12 at 8:17
    
If your argument were correct, then you would not (only) have shown that $\mathbf N$ is uncountable, but in fact that mathematics is inconsistent (so in fact every statement would be both provable and provably false). That is because $S$ being uncountable means there does not (cannot) exist a bijection between $S$ and $\mathbf N$, and as you already noticed such a bijection does exist when $S=\mathbf N$ (the identity). –  Marc van Leeuwen Feb 7 '12 at 13:37
add comment

1 Answer

up vote 31 down vote accepted

Your error is in the assertion:

... we will end up with a sequence of non-zero digits, which forms a valid Natural number...

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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