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:
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:
0001 0 0
000 1 01
00 0 102
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?