Re: Cantor Diagonal Proof

On 4/6/25 1:04 PM, Richard Heathfield wrote:

On 06/04/2025 17:24, Mike Terry wrote:

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.

 Nevertheless, that's precisely what Mr D'Oliveiro is talking about. From the start of the thread:
 "The Cantor diagonal construction is an algorithm for computing an incomputable number. But if there is an algorithm for computing the number, then it is by definition a computable number."
 <snip>

First, Cantor's Diagonal Argument wasn't about construable numbers, but about numbers being countable.
It is a later analysis that shows that it is unconstructable.
And from what I see, the issue is that while each of the numbers in the list could be defined as constructable, in that a algorithm exists that given n, it will give at least n digits of that number, there doesn't need to be a master algorithm, that given k and n gives the first n digits of the kth number, that can be shown to cover the full set of constructable numbers (but perhaps an countable infinite subset of them). Without that master algorithm, the method of constructing the diagonal isn't actually an implementable algorithm.
We can't just iterate through all possible machines, because not all machines are halting, let alone meet the requirements for the construction machines.
Thus, we don't have an actual algorithm that makes the diagonal number constructable.

 

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

 It is an attempt to formalise what I believe to be what the OP considers to be the relevant algorithm for arriving at the diagonal.
 

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

 It's just shorthand. I'm very willing to consider suggestions for alternative ways to convey meaning so succinctly.
 

The diagonal definition is just that: a definition, not a step by step sequence of anything.

 Yes. We don't have to run alongside Achilles.
 

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.

 Mr D'Oliveiro, however, is.
 

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.

 Yes. Because of the way "computable" is defined, the same proof works for computable numbers and suffices to debunk Mr D'Oliveiro.
 

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.

 No, but Mr D'Oliveiro did.
 

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.

 Yes.
 

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.

 It's okay; we're playing with the whole set.
 

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

 Actually, it does. I got it for Christmas in 1996. Last time I looked it was somewhere in the loft.