Path: ...!weretis.net!feeder9.news.weretis.net!news.quux.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Andy Walker <anw@cuboid.co.uk>
Newsgroups: comp.theory
Subject: Re: Cantor Diagonal Proof
Date: Sun, 6 Apr 2025 17:22:28 +0100
Organization: Not very much
Lines: 48
Message-ID: <vsu9o4$lqc0$2@dont-email.me>
References: <vsn1fu$1p67k$1@dont-email.me>
 <7EKdnTIUz9UkpXL6nZ2dnZfqn_ednZ2d@brightview.co.uk>
 <vsng73$27sdj$1@dont-email.me>
 <gGKdnZiYPJVC03L6nZ2dnZfqn_udnZ2d@brightview.co.uk>
 <vsnk2v$2fc5a$1@dont-email.me> <vsnmtg$2i4qp$3@dont-email.me>
 <vsno7m$2g4cd$3@dont-email.me> <vsnp0o$2ka6o$2@dont-email.me>
 <vsnpv4$2g4cd$6@dont-email.me> <vsntes$2osdn$1@dont-email.me>
 <vsntv3$2paf9$1@dont-email.me> <vso1a0$2sf7o$1@dont-email.me>
 <vso2ff$2tj1d$2@dont-email.me> <vso3rj$2vems$2@dont-email.me>
 <vso4gh$2vg3b$1@dont-email.me> <vsqmlb$1ktm5$6@dont-email.me>
 <vsr1ae$1pr17$2@dont-email.me> <vst4nm$8daf$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 06 Apr 2025 18:22:28 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="1c5555904f7d3c872cf814db227a42ec";
	logging-data="715136"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19U9TS+8PC8hE+V6nlAhDLb"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:ZEpnkQyCcF6+JqRvp5K6DXBZEeM=
Content-Language: en-GB
In-Reply-To: <vst4nm$8daf$2@dont-email.me>
Bytes: 3995

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