Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: Cantor Diagonal Proof
Date: Sat, 5 Apr 2025 10:10:44 +0300
Organization: -
Lines: 33
Message-ID: <vsql1k$1lpck$1@dont-email.me>
References: <vsn1fu$1p67k$1@dont-email.me> <vso3j4$2vbn4$1@dont-email.me> <vso3ov$2vems$1@dont-email.me> <vso4oc$30ine$1@dont-email.me> <vspb09$75m8$6@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 05 Apr 2025 09:10:45 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="f9307d8d2dc3a84618ee3d69a5f67187";
	logging-data="1762708"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+/thl9I6l+2X73TmtE/TdE"
User-Agent: Unison/2.2
Cancel-Lock: sha1:LJIySLrJLJgUw1IyI7n5xsN+byw=
Bytes: 2212

On 2025-04-04 19:13:13 +0000, Lawrence D'Oliveiro said:

> On Fri, 4 Apr 2025 11:20:28 +0300, Mikko wrote:
> 
>> On 2025-04-04 08:03:44 +0000, Lawrence D'Oliveiro said:
>> 
>>> On Fri, 4 Apr 2025 11:00:36 +0300, Mikko wrote:
>>> 
>>>> On 2025-04-03 22:18:38 +0000, Lawrence D'Oliveiro said:
>>>> 
>>>>> The Cantor diagonal construction is an algorithm for computing an
>>>>> incomputable number.
>>>> 
>>>> Can you prove that it computes an incomputable number?
>>> 
>>> It’s trying to come up with a number that cannot fit into a set with
>>> cardinality ℵ₀. The cardinality of the computable numbers is the same
>>> as that of the integers, which is ℵ₀.
>> 
>> It is also the cardinality of rationals but not of reals. Cantor's proof
>> is that for each list of reals one can construct a real that is not in
>> the list.
> 
> That proof doesn’t quite work, because at any point in the construction,
> the number can be shown to match some later item in the list. The mismatch
> with all items in the list is only demonstrated when the proof completes.
> But the proof never completes. Therefore there is no mismatch. QED.

The proof is finite and complete.

-- 
Mikko