If you know the proof you probably know that you don't actually use the "(n+1) mod 10" mapping, you use that mapping but instead remap all 8's into something else, like 3, in particular you don't remap 8's into 9's to avoid the "99999..." tail problem. In fact if you like you can just use the following mapping: 0->1, {1,2,3,4,5,6,7,8,9}->0. Also, for the starting representations you simply replace all expansions with an infinite tail of "9999...", as for every such representation there exists a representation that does not end in "9999...". This makes the decimal expansions unique.
All the name-able reals are obviously countable, this has a deep connection with the Löwenheim–Skolem theorem: https://en.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skolem_...
1: 1
2: 2
3: 3
4: 4
5: 5
...
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).
There already exists at least one mapping of integers into integers, the identity mapping. Hence a correct proof that there exists no mapping of integers into integers (proving the opposite claim) would also tell us that FOL+ZFC (first order logic with the standard axioms of set theory) is inconsistent, regardless of whether Cantor's diagonal argument features in that proof.
In the other direction, if FOL+ZFC is inconsistent, it's trivial to write a proof that shows that integers cannot be mapped to integers that features Cantor's diagonal argument in it.
So the existence of a proof that shows that no mapping of the integers to the integers exists is equivalent to FOL+ZFC being inconsistent, and no-one has yet found FOL+ZFC to be inconsistent, or expects this to be the case.
If a proof technique could prove untrue theorems, it wouldn't be very convincing, would it?
I hope someone comes here to argue that Vitalik is right against me.
In the second paragraph, there is a faulty assumption that all real numbers are computable.
> If a proof technique could prove untrue theorems, it wouldn't be very convincing, would it?
But Cantor's diagonalization argument can be used to prove that the integers cannot be mapped to integers if and only if every theorem is true.
That would resolve it. I found the expositions I heard unconvincing (even one in person by a famous mathematician), but it makes sense the flaws were in the abbreviation (and/or me), not in Cantor.
> What part of the theorem are you uncomfortable with?
As I've said, it's not the theorem, but this proof of it. Not a particular part, but that this proof technuque could prove something that is untrue. i.e. there was no condition to prevent it being applied to integers.
Here's a sketch of the argument, from my cousin comment: https://news.ycombinator.com/item?id=25111003
Looks like it's prevented from being applied to integers by: a diagonal of an infinite list requiring numbers with infinite digits. Which integers don't have.
The technical step is where this fails: is there a bijection f that maps integers to their representation (as you have constructed) that also maps the sequence not in the list back to an integer? We don't have that because f(f\inv(x)) must be on the list, but x is not on the list. (For example, no integer is represented by the sequence 1111... in the representation you gave; every integer's representation must end in 0000..... But the result is more general, that no matter what representation you choose, the diagonal sequence is not the representation of any integer.)
So we see that the diagonal argument just tells us that there are more binary sequences than integers.
On the other hand, this tells us at least that: there are more binary sequences than integers.
It can be shown that there is a 1-1 correspondence between binary sequences not ending in infinite consecutive zeros, and real numbers (e.g. as constructed by dedekind cuts). Now, the binary sequences not ending in infinite consecutive zeros are the representation of certain rational numbers so must be a subset of the rational numbers. So since the set of binary sequences is uncountable, but the set of rational numbers is countable, the set of real numbers is at least as large as an uncountable set less some countable set, which is again uncountable. Hence the real numbers are uncountable.
> The technical step is where this fails: is there a bijection f that maps integers to their representation (as you have constructed) that also maps the sequence not in the list back to an integer?
> We don't have that because f(f\inv(x)) must be on the list, but x is not on the list.
Or: the diagonal complement is not an integer, so doesn't enter into any mapping of integers to integers.
In contrast, for the presentation I saw for reals, the diagonal complement with infinite digits is of course a real, so doesn't have this problem.
BTW: the presentations I've seen used a randomly-ordered list, which avoids the all-1 diagonal. Not sure why they this - but it led to my question. Anyway, all-1 is a real, but not an integer, so that answers my question.
Thanks for taking the trouble and time to help unravel my question!
Your last para, I think, is a simpler way around the article's problem that a real can have mor one representation in. infinite digits. e.g I think .999... = 1.000...