Re: Cantor Diagonal Proof

On 04/04/2025 05:24, Lawrence D'Oliveiro wrote:

On Fri, 4 Apr 2025 04:35:59 +0100, Richard Heathfield wrote:
 

The Cantor argument constructs a number that is not
in the input list and thus proves that the input list, no matter how
large, is incomplete.

 But that proof takes an infinite number of steps.

No, it takes the ability to reason about an infinite number of steps. Just like $\int_0^infty_\frac{1}{2^n}$ we can work out what the answer is without having to spend infinite time on it.

At every point, the
probability that the N digits computed so far match some number later in
the list is 1.

Counter-example follows.
Input list:
1111
2222
3333
4444
Construction:
2
x3
xx4
xxx5
After computing N digits we find a match for a later number only once, for 2. There are no matches for 23, 234, or 2345.
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within