| Not sure if fatal to your argument, but zero doesn't need to be remapped: showing two sets can't be mapped doesn't require every element to be remapped. But maybe your point about needing infinite digits is the reason? Anyway, here's a sketch of the "proof": list the natural numbers, in binary, simply in order, from zero onwards. But written in reverse, eg 100 (4) is written 001 [NB: the list will grow longer faster than the length of each number, so the diagonal will be all zeros.] now construct the "diagonal" number: taking its ith digit as the complement of the ith digit of the ith number in the list. This will be all 1's. This number isn't in the list, because one of its digits differs from each one of them, by definition. Therefore, this list of the natural numbers can't enumerate all the natural numbers. Perhaps the flaw is simply that although there are infinitely many natural numbers, each of them only has finite digits. That all-1 diagonal has infinite digits, so it isn't a natural number (as you say). |