Re: Cantor Diagonal Proof

On 15/04/2025 05:42, Lawrence D'Oliveiro wrote:

Here’s my counterexample list: write out the whole numbers
(non-negative integers) from 0 in increasing order, and flip the
digits of each one so that the digit from the 10⁰ place goes to the
10¯¹ place, 10¹ to 10¯² etc:
      0.0000000000000...
     0.1000000000000...
     0.2000000000000...
     0.3000000000000...
     ...
     0.9000000000000...
     0.0100000000000...
     0.1100000000000...
     0.2100000000000...
     0.3100000000000...
     ...
     0.9100000000000...
     0.0200000000000...
     ...
 Notice an interesting property of the list:
* If you look at the first digit after the decimal point, then in
   every run of 10 consecutive list entries, you will find every
   possible value of that digit.
* If you look at the first two digits after the decimal point, then in
   every run of 100 consecutive list entries, you will find every
   possible combination of values of those two digits.
...
* If you look at the first N digits after the decimal point, then in
   every run of 10**N consecutive list entries, you will find every
   possible combination of values of those N digits.
 (Combinatorial explosion? Of course it’s a combinatorial explosion.
But there’s plenty of room for a combinatorial explosion or two, or
many, in an infinite list!)

No problem so far - your list is well defined and has the properties you claim.

 This is a priori not a *complete* list of all the reals (the original
point of the Cantor construction). You’d think it would make things
easier for the Cantor construction, but it doesn’t.
 Step 1 of the Cantor construction: choose a digit in the 10¯¹ place
different from that of the first item in the list. There are 9
possibilities we could pick. But all the 10 possibilities for that
first digit occur in the following 10 numbers, so our pick will
definitely match one of them.

Correct.  You are just showing that the FINITE PREFIX consisting of the first digit of the Cantor "anti-diagonal" occurs in your list.
You are NOT showing that the full anti-diagonal occurs in the list.  That would have to match not only the finite prefix digits, but additionally every digit position including those for all digits beyond the first place.

 Step 2: choose the next digit, in the 10¯² place, different from that
of the second item in the list. There are, again, 9 possibilities we
could pick. But all the 100 combinations of possibilities for the
first two digits occur in the following 100 numbers, so our picks so
far will definitely match one of them.

Correct.  You are just showing that the FINITE PREFIX consisting of the first 2 digits of the Cantor "anti-diagonal" occurs in your list.
You are still NOT showing that the full anti-diagonal occurs in the list.  That would have to match not only the first two digits, but additionally every digit position including those for all digits beyond the second place.

 And so on: at step N, we pick a digit in the Nth decimal place, to be
different from that of the Nth number in the list. But all the 10**N
possibilities for the digits we have picked so far occur in the
following 10**N numbers, so the number we have constructed so far will
provably match one of them.

Correct.  You are just showing that the PREFIX consisting of the first N digits of the Cantor "anti-diagonal" occurs in your list.
You are still NOT showing that the full anti-diagonal occurs in the list.  That would have to match not only the finite prefix digits, but additionally every digit position including those for all digits beyond the N'th place.

 Note this is a proof by induction: if our choices at step N match some
existing entry in the list, then so will the addition of our next
choice at step N + 1. Since our first choice already matches some
existing entry in the list, it follows that, however many digits we
choose, the result will always match some existing entry in the list.

It is not a proof by induction as it makes no use of an induction hypothesis PHI(n), and does not have any essential induction step PHI(n) --> PHI(n+1).  Instead it just establishes that for any n PHI(n) holds, directly from the construction of your starting list.
Well, let's not get hung up on this - it's not a proof by induction, but it is established that PHI(n) holds for all n, where
    PHI(n):   the n-digit prefix of anti-diag matches the n-digit prefix
              of some entry in the list.
Note:  the entry matched in PHI(n) in general differs for each n, becoming further and further down the list as n increases.
Note:  there is no list entry index N which works for all n in the PHI definition. (The matched entry in the list does not "stabilise"/converge as n increases.)

 So even in a list which we already know does not contain every
possible real number, the Cantor construction fails to find one of the
missing ones.

Nonsense!  RH's example using your very list constructs the anti-diagonal 0.111111... which is NOT IN YOUR LIST.  Cantor's proof works fine...
You misunderstand what it means for a number (such as the Cantor anti-diagonal D) to "be in the list" or not.
A number D, having digits D[n], n=1,2,3,4,... , is in the list of real numbers L[m]" if
     there exists a list index m such that
        for ALL digit positions n,
           D[n] = L[m][n].
        [Or put more simply, that D = L[m]]
Note the quantification order:  FIRST we choose one single list index position m, and then the digits at EVERY digit position of that entry have to match those of D.  You have this backwards - you're trying to FIRST choose a digit position, and THEN choose (dependent on the digit position) a list index number which matches in some way (namely a finite prefix match).  That's completely wrong.
Regards,
Mike.