Re: Cantor Diagonal Proof

On 2025-04-06 10:52:50 +0000, Richard Heathfield said:

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.

The number D is not computable if the list C is not. The counter-assumption
was that there is a list of all computable numbers but not that there is a
computable list of all computable numbers. As the nuber D is not computable
its absense in C is not a contradiction.
--
Mikko