Cantor was Wrong: debunking the infinite set hierarchy | Hacker News Reader

Cantor was Wrong: debunking the infinite set hierarchy

vitalik.ca

12 pointsmasteranza15 comments

This is obviously a joke by Vitalik Buterin, also it's a good test as to whether someone actually understands the proof :)

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

I think the error is much deeper here: he presumes that every number in R can be produced by a program, i.e. every real number is computable.

That is, I think, the second part of the joke, all required to "prove" the thesis at the end, namely that halting problem is solvable :)

Why can't Cantor's diagonalization argument be used to show the integers cannot be mapped to the integers?

What would you re-map 0 into? If it's re-mapped into anything else than 0 then you'll potentially end up with an infinite sequence of digits, i.e. not an integer. And of course it has to be re-mapped into something else than itself. This would fail on the following list:

In other words - after getting the re-mapped diagonal you end up with an object that's potentially no longer an integer - it can be infinitely long.

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

I don't know if you're referencing something in the article linked, but taking your statement alone, it's not that this cannot be shown, but that nobody has shown it, and nobody expects it to ever be shown.

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.

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?

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.

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

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.

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

Funny :)

I hope someone comes here to argue that Vitalik is right against me.

Don't know the author well enough to know if this is a joke. However, saying something is "easy to see" that has not been accepted for a century must be satire...

In the second paragraph, there is a faulty assumption that all real numbers are computable.

Look at the date of the post :)))

Reply on news.ycombinator.com