[hyperpallium2]

I was questioning Cantor's argument, that it appears to be able to show something obviously untrue. Since his approach is widely accepted, I feel there must be some reason it can't be applied to integers.

If a proof technique could prove untrue theorems, it wouldn't be very convincing, would it?

[jhanschoo]

The paper this post is concerned with is satirical, and Cantor's argument showing the uncountability of real numbers is correct. Note that there are a couple technical steps skipped by some expositions of Cantor's argument. What part of the theorem are you uncomfortable with?

> 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.

[hyperpallium2]

> Note that there are a couple technical steps skipped by some expositions of Cantor's argument.

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.

[jhanschoo]

Observe that all Cantor's diagonal argument shows is that given any countable list of sequences in a finite alphabet (i.e. whose elements are from a finite set, e.g. binary or decimal), you can construct a particular sequence in that alphabet not in the list.

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.

[hyperpallium2]

I had to find time to think about this.

> 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...