If a proof technique could prove untrue theorems, it wouldn't be very convincing, would it?
> 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.
