[zelah]

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.

[lisper]

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

[chriswarbo]

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

[lisper]

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

[kd0amg]

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

[yongjik]

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.