Re: Cantor Diagonal Proof

On Sat, 5 Apr 2025 11:40:14 +0100, Andy Walker wrote:

It does succeed with every possible list.

Here’s a 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...
    ...

This is not a *complete* list of all computable numbers, let alone 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.

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.

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.

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.

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

QED.