Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.theory > #133344

Re: Cantor Diagonal Proof

Cross-posted to 2 groups.

Followups directed to: sci.math

Show all headers | View raw

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.

Back to comp.theory | Previous | Next — Next in thread | Find similar | Unroll thread

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 16:59 +0100

csiph-web