Re: Cantor Diagonal Proof

On 06/04/2025 11:52, Richard Heathfield wrote:

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.

Cantor made no reference to computability or computable numbers.  His list was list of all real numbers (computable or otherwise; computable numbers weren't invented as a concept in his days).
In fact, I don't think Cantor proposed the argument for uncountability of real numbers in this form, although it's usually referred to as "Cantor's list".  He had a simular argument but applied to a sequence of R and B symbols (red/black??), which shows the set of such sequences is uncountable.  He also had a totally separate proof of the uncountability of the reals which was not based on their digit representation.
Still, everyone calls it "Cantor's proof", even if he never actually proposed it in that form...

 2. Let D be the Cantor diagonal, eg via
 for(n = 0; n <= inf; n++)
{
   D[n] = (C[n][n] + 1) % 10;
}

You are writing the above as though it is some kind of step-by-step program to be executed.  That's a source of confusion amongst certain non-mathematicians, particularly those with a programming perspective on things.  (Not that you're confused - I'd just avoid such notation in case others are confused.)
The diagonal definition is just that: a definition, not a step by step sequence of anything.

 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.

Cantor was not concerned with computability.  His proof assumes we have the list as in (1), and constructs (defines) a new real number which is manifestly not in the list using the well known diagonal argument.
There is no error with the construction of D, given the list.  Depending on exact wording of the proof, it either shows that every list of reals misses at least one real number [the "anti-diagonal"], or that a contradiction is reached from the assumption that the original list was complete [the new anti-diagonal being a real number both in the list and not in the list] and so the assumption of completeness of the list was false.

  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.
 

Hmmm, maybe you're talking about applying Cantor's argument to the list of computable numbers? Cantor never did that.  If we do this, we can certainly start with a list of computable numbers which is complete, since there are only countably many such numbers.  Then the anti-diagonal argument produces a new (non-computable) number that is not in the list.
It might seem that the number produced must be computable because the anti-diagonal "computes" it, but the anti-diagonal "computation" would only work given infinitely many digits of data out of the list.  (E.g. the whole list that you've called C[inf][inf] could be represented on a tape, or perhaps just the diagonal etc. but in any case the job can't be done with only a finite amount of data.
Or perhaps we might think that a "computable list" of computable numbers could be constructed where a single TM can somehow generate all the C[inf][inf] on request (no extra data being input other than the row/col indices of the required entry).  Then we could have one single TM that calculates all the anti-diagonal digits with no further data input from the expanded list since it can just calculate those digits as required.  That would present a contradiction since the new anti-diagonal number would then be computable!  But such a "computable list" is just wishful thinking and does not exist...
Mike.