Re: Cantor Diagonal Proof

On 4/15/25 12:42 AM, 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!)
 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.
 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 real number, the Cantor construction fails to find one of the
missing ones.
 QED.

Your problem is induction doesn't prove what you want. Remember the results of an induction is a proof that the property holds for all Natural Numbers.
Your property that you are examining is that your diagonal, to its first N digits, is in the list, so your proof is that any finite initial string of your number is in the list, which it is,
Induction does NOT prove that "at infinity" the property holds, as "infinity" isn't a Natural Number.
Sometimes we can move from all finite to the full set, but that needs the prior proof that the set is just countably infinite. Since the ultimate proof of that is what you are trying to do, you can't use that, as that is the fallacy of assuming the conclusion.