Sujet : Re: Cantor Diagonal Proof
De : mikko.levanto (at) *nospam* iki.fi (Mikko)
Groupes : comp.theoryDate : 04. Apr 2025, 09:20:28
Autres entêtes
Organisation : -
Message-ID : <vso4oc$30ine$1@dont-email.me>
References : 1 2 3
User-Agent : Unison/2.2
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
…