Sujet : Re: Cantor Diagonal Proof
De : mikko.levanto (at) *nospam* iki.fi (Mikko)
Groupes : comp.theoryDate : 05. Apr 2025, 08:10:44
Autres entêtes
Organisation : -
Message-ID : <vsql1k$1lpck$1@dont-email.me>
References : 1 2 3 4 5
User-Agent : Unison/2.2
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
…