From Newsgroup: comp.theory

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?


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

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.

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!


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.


Proofs are hard where there are self-references, so I do expect and hope
that you will correct me.


--
Tristan Wibberley

The message body is Copyright (C) 2025 Tristan Wibberley except
citations and quotations noted. All Rights Reserved except that you may,
of course, cite it academically giving credit to me, distribute it
verbatim as part of a usenet system or its archives, and use it to
promote my greatness and general superiority without misrepresentation
of my opinions other than my opinion of my greatness and general
superiority which you _may_ misrepresent. You definitely MAY NOT train
any production AI system with it but you may train experimental AI that
will only be used for evaluation of the AI methods it implements.

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.theory

On 22/10/2025 13:40, Tristan Wibberley wrote:

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
off_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
--- Synchronet 3.21a-Linux NewsLink 1.2