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...

    [... snippage ...]

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.

There's a hint to your mistake in "so far".  The constructed
number will not continue to match any particular member of the list
indefinitely.
[...]

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.

Contrariwise, if we assume by way of an example that 0 -> 1, the
constructed number is 0.11111....  In real maths, that is 1/9;  and is
different from any number in your list [which has the form N/10^k for
some integers N and k].  It is true that numbers starting 0.111 occur
every 10^3 elements of your list, and numbers starting 0.11111 occur
every 10^5 elements, but the specific number 1/9 never occurs.  If you
somehow sneak 1/9 into your list, then the constructed number changes
to match, and again never occurs in your new list.
If, as in your example, the list is "everywhere dense" [a term of
art] then any given prefix of the constructed number will occur a
countable infinity of times, but the actual constructed number will differ
from all of them if you continue the construction -- specifically, it will
differ from the Nth element of the list in the Nth decimal place.  [As
before, it's necessary to avoid the 0.999... == 1.000... ambiguity in the
real numbers, but that's easy and left as an exercise.]
--
Andy Walker, Nottingham.
    Andy's music pages: www.cuboid.me.uk/andy/Music
    Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Rimsky-Korsakov