Path: 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: Fri, 4 Apr 2025 11:20:28 +0300
Organization: -
Lines: 23
Message-ID: <vso4oc$30ine$1@dont-email.me>
References: <vsn1fu$1p67k$1@dont-email.me> <vso3j4$2vbn4$1@dont-email.me> <vso3ov$2vems$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 04 Apr 2025 10:20:28 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="670086d25131323072cd2a1bcb3678f0";
	logging-data="3164910"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18i09bCNTxycztz3L+EnDJx"
User-Agent: Unison/2.2
Cancel-Lock: sha1:BUK7cuFH8BWqfWtI52XRWQmO01c=

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. But the real that is not in the list is computable only if the
list is.

-- 
Mikko