Re: Cantor Diagonal Proof

On 06/04/2025 18:04, 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>
 

Sure, but... I'm still not clear on whether OP is expecting/requiring the Cantor list to be a list of computable numbers.  I don't believe he has stated that anywhere...  He just keeps saying the missing number is computable.

>
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 "D[n] = (C[n][n] + 1) % 10" bit is no problem, but the for loop is definitely encouraging people to think of the whole thing as some kind of supertask, which it's not.  OP continually refers to the series of steps, and what we see specifically at step n, rather than the specific missing real number D which is defined in the proof.
I'd have just said that the D was the unique real number whose n'th digit is
    D[n] :=   5  [if   C[n][n] != 5]
              6  [otherwise]
(no need for procedural loops...  also sidesteps the whole 0.999999... discussion we've thankfully not had)  Of course there are endless alternatives to say the same.

 

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.

I don't see anywhere that he says the list is a list of computable numbers - just where he says the missing number must be computable.

 

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.

OP's main problem seems to be that he doesn't understand that a computable real has a /finite/ definition via an algorithm/TM, not a sequence of ever larger TMs that can each compute just finite digit prefixes.  Computing the anti-diag requires the Cantor list as input, which cannot be packaged into a finite amount of data.  Maybe OP has something else in mind but simply hasn't expressed it anywhere so people can't tell what he's actually getting at.  (A bit like assuming the numbers in the list are computable without bothering to actually say that. :) )  Or maybe OP is trolling or a just confused about things, hard to say.

 

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.

I never get useful presents like that :(   I was given a free module one Christmas when times were hard!
Mike.