Path: ...!weretis.net!feeder9.news.weretis.net!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: Cantor Diagonal Proof
Date: Tue, 15 Apr 2025 07:01:09 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <4e59e78d6e1b43e19015058f465de06e04ba135d@i2pn2.org>
References: <vsn1fu$1p67k$1@dont-email.me> <vthad1$3oh15$3@dont-email.me>
 <9c27b08cca9d0fca87e57bcabc3412c80ff7a4f1@i2pn2.org>
 <vtk37d$295ku$7@dont-email.me>
 <99bd9c3545fdcc03cf33152ee0db852edbe1e23d@i2pn2.org>
 <vtko3u$2u0tr$6@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 15 Apr 2025 11:05:26 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="446610"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
In-Reply-To: <vtko3u$2u0tr$6@dont-email.me>
X-Spam-Checker-Version: SpamAssassin 4.0.0
Content-Language: en-US
Bytes: 4992
Lines: 85

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.