Re: Cantor Diagonal Proof

On 06/04/2025 06:50, Lawrence D'Oliveiro wrote:

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.

On the contrary, it finds a new number precisely where Achilles overhauls the tortoise. After infinitely many steps, it arrives at a number not on the list, and that number is not computable because it requires infinitely many steps to identify it.
How can I be sure it's not on the list? Simple. You pick out the number you think it matches (in position M for Match, say), and we'll find that for any M it differs from our diagonal in the Mth digit.
You can /place/ that number later in the list if you like, and we can /still/ construct a diagonal that differs from /that/ number.
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within