Re: Cantor Diagonal Proof

On 06/04/2025 11:29, Mikko wrote:

On 2025-04-05 07:38:19 +0000, Lawrence D'Oliveiro said:
 

On Fri, 4 Apr 2025 09:16:17 +0100, Richard Heathfield wrote:
>

Since all elements (except your two openers) begin with a 3, none of
them start 12, and so after just two iterations we have already
constructed a number that's not in the infinite list.

>
Remember that the hypothesis of the Cantor “proof” is that the list is
already supposed to contain every computable number. The fact that the
contruction succeeds for your list examples does not mean it will succeed
with mine.

 How can Cantor's construction fail to succeed on a list?

As I understand it, his argument can be summarised as follows:
1. Let C[inf][inf] be a list of all the digits of all the computable numbers.
2. Let D be the Cantor diagonal, eg via
for(n = 0; n <= inf; n++)
{
   D[n] = (C[n][n] + 1) % 10;
}
3, Because we have computed D, it is a computable number, and therefore it must have an entry in C[, so the construction of D must somehow be in error.
The flaw, of course, is in overlooking that we required infinitely many steps to derive D. for(n = 0; n <= inf; n++){whatever} is not an algorithm, because by definition algorithms must have at most finitely many steps.
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within