Hacker News Reader

Comment by zelah | Hacker News Reader

I will just diagonalize forever before I give the set to Cantor. If he claims that he can diagonalize the set to generate a new number not in the set then I will say "Oh, yeah - I missed one. I wasn't really done after all. Give it back to me and I will add some more to it before you get your hands on it!". As you can see, Cantor will never get a list because I will never really be done generating it.

I could just give him the list and say that whatever he adds is precisely what I would have added had I continued. This is like an infinite lazy list in programming.

View on HN

> Cantor will never get a list because I will never really be done generating it.

That would be true even if you weren't diagonalizing because the list is infinite. In fact, just a single item in the list is potentially infinite. So you can't generate the whole list regardless.

What you have to do is to produce an algorithm that takes any two natural numbers i and j as input and produces as output in finite time the j'th digit of the i'th number in the list. Because you have to produce your digit in finite time you can only diagonalize a finite number of times, so Cantor can always do you one better and produce a number not on your list.

Why is it that Cantor can do an infinite procedure of diagonalization but I can't? If he can diagonalize then I can too. Is it possible that Cantor's "algorithm" is not really an algorithm? Knuth says an algorithm must be correct and must also terminate.

Regardless, I have a lot to ponder.

Okay, let me try to write these "algorithms" in a concrete term.

Assume that you have a way of generating a sequence R_1, R_2, R_3, ... of real numbers in [0, 1]. (For simplicity, let's just consider [0, 1], because it still has the same cardinalityas R.) You have your "algorithm":

    generate_digit(i, j):
        Somehow compute the j'th digit of R_i.
        return the digit

You are allowed to spend infinitely long time to return each digit. (That is, you can use constructions that are not even computable in finite time, as long as you can prove that given i and j, there is exactly one digit that satisfies your criterion.)

Cantor's objective is to defeat your algorithm by generating a real number not in the list. Similarly as above, it can be written as a function that returns the j'th digit, given j. Behold it in its full glory:

    defeat_indexing(j):
        digit = generate_digit(j, j)
        return (digit + 1) % 10

That's it.

Cantor is playing by the exact same rules that you are. His burden is: given an integer i, produce in finite time the i'th digit of a real not in your list. (He can't produce the whole thing in finite time because it's infinite, obviously.) He does this by using your algorithm to produce the i'th digit of the i'th row and adds one to it (mod 10).

> given an integer i, produce in finite time the i'th digit of a real not in your list

Yes; to be clear, my point is simply that there are two variants of this task:

- Given an integer i and our list (or the infinite procedure that generates it), then the task is easy since we can diagonalise.

- Given an integer i and no knowledge of our list, the task becomes impossible, since the supposed "real not in your list" is actually independent of the list (by definition); hence we're free to choose any list we like, including waiting until after the supposed counter-example has been generated, and sticking that at the head of our list.

What does this prove though? That no specific real is guaranteed to be left out of every list? Was that ever in dispute?

> my point is simply that there are two variants of this task

There are infinite variants of this task. But only one of them is mathematically interesting with respect to the claim that the reals cannot be put into one-to-one correspondence with the naturals.

> including waiting until after the supposed counter-example has been generated

Obviously, if I give you a real you can then generate a list that includes that real. That isn't very interesting.

Reply on news.ycombinator.com