Re: Cantor Diagonal Proof

From	Richard Heathfield <rjh@cpax.org.uk>
Newsgroups	sci.math
Subject	Re: Cantor Diagonal Proof
Date	2025-10-22 14:29 +0100
Organization	Fix this later
Message-ID	<10dam7c$lah6$1@dont-email.me> (permalink)
References	<vsn1fu$1p67k$1@dont-email.me> <10dajcd$j82n$1@dont-email.me>

Show all headers | View raw

On 22/10/2025 13:40, Tristan Wibberley wrote:
> The message body is Copyright (C) 2025 Tristan Wibberley except
> citations and quotations noted. All Rights Reserved except as noted in
> the sig.
> 
> 
> On 03/04/2025 23:18, Lawrence D'Oliveiro wrote:
>> The Cantor diagonal construction is an algorithm for computing an
>> incomputable number.
> 
> Doesn't it merely /define/ the number?

It doesn't even do that.

Cantor's diagonal argument proves that uncountable sets exist. At 
no point did he claim that the number the argument computes is 
incomputable.

> I'm still unconvinced that he successfully did even that anyway.

He didn't try. An existence proof doesn't have to define a number.

> take these descriptions:
> 
>    f_0 is the defining sequence of numbers
> 
>    g is the sequence of generated "new" numbers, generated as they
>    say cantor described (I haven't read his work directly)
> 
>    f_1 is some choice of numbers
> 
>    even(n) and odd(n) are as you'd normally expect
> 
> 
> then I can provide an f_0:
>    where f_0(n) = case n of
>              even(n) -> f_1(n/2)
>              odd(n) -> g((n-1)/2)
> 
> here, every generated "new" number is eventually included in the list.

And yet your list remains incomplete.

> To show that the set of reals is larger than the set of naturals one
> would have to show that there's no definition of f_1 such that it
> contains all the reals!

No, you'd only have to show that you can't place the reals in 
one-to-one correspondence with the integers.

> Which is not to say I think the reals are countable (I remain
> undecided), but just that I think the usual proof of their
> uncountability is insufficient.

It suffices.

-- 
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

Thread

Re: Cantor Diagonal Proof Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2025-10-22 13:40 +0100
  Re: Cantor Diagonal Proof Richard Heathfield <rjh@cpax.org.uk> - 2025-10-22 14:29 +0100
    Re: Cantor Diagonal Proof Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2025-10-22 16:02 +0100
      Re: Cantor Diagonal Proof Julio Di Egidio <julio@diegidio.name> - 2025-10-22 17:17 +0200
      Re: Cantor Diagonal Proof Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2025-10-22 17:26 +0100
    Re: Cantor Diagonal Proof WM <wolfgang.mueckenheim@tha.de> - 2025-10-23 16:51 +0200
  Re: Cantor Diagonal Proof Julio Di Egidio <julio@diegidio.name> - 2025-10-22 16:19 +0200
    Re: Cantor Diagonal Proof Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2025-10-22 17:32 +0100
    Re: Cantor Diagonal Proof WM <wolfgang.mueckenheim@tha.de> - 2025-10-23 16:56 +0200
      Re: Cantor Diagonal Proof: un-_Countable_ or un-_Cartesian_? Ross Finlayson <ross.a.finlayson@gmail.com> - 2025-10-23 12:27 -0700
  Re: Cantor Diagonal Proof "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-10-22 12:15 -0700
  Re: Cantor Diagonal Proof wm <wolfgang.mueckenheim@tha.de> - 2025-10-23 16:34 +0200
    Re: Cantor Diagonal Proof Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2025-10-23 20:43 +0100
      Re: Cantor Diagonal Proof WM <wolfgang.mueckenheim@tha.de> - 2025-10-24 22:35 +0200

csiph-web