Re: Zenkin's paper on Cantor

From: Daryl McCullough (daryl_at_atc-nycorp.com)
Date: 10/07/04 

Date: 7 Oct 2004 04:08:50 -0700

Eray Ozkural exa says...
>
>daryl@atc-nycorp.com (Daryl McCullough) wrote

>> You can give me a *procedure* which, given a number n
>> returns the nth real number (between 0 and 1, for simplicity),
>> which in turn is a procedure which, given a number m, returns
>> the mth bit of the binary expansion of that real.
>
>Yes, of course, Daryl, that is quite obvious.

Then I don't understand why you are claiming that Cantor's proof
is nonconstructive. It can be recast into a form that is completely
in terms of *computable* functions:

   For any total computable function l which enumerates (indices of)
   total computable functions, there is a total computable function d
   which is not enumerated by l.

>Now, giving the list in this fashion would be potential infinity,
>since it is compressed in a finite nonhalting program. My post is in
>error, the second proof also can be said to be valid from a
>constructivist perspective, if the reals chosen are deliberately taken
>to be computable in exactly this way.

I think that there is a subtle distinction about the "constructivist
perspective" that you are missing. Constructivism doesn't *assume*
that all functions are computable. Constructivism doesn't assume
anything unless there is a constructive proof that it is true, and
there is no proof that all functions are computable. Rather, constructivism
is a discipline on what constitutes a *proof* of a statement.

So in proving a statement of the form

    forall x, exists y, Phi(x,y)

a constructivist must come up with a procedure Y(x) which computes
y given x, but the constructivist doesn't assume that x must be
given by a procedure. The burden of proof (to come up with an
explicit construction) is on the person proving something.

Similarly, about the existence of "actual infinity": Constructivists
don't assume that there is no actual infinity, but they use no such
object in their proofs.

>But I do not think that Cantor's original proof is in fact
>constructive in the sense of *constructivism*.

Well, constructivism was not invented at Cantor's time, but there
is nothing nonconstructive about Cantor's proof. 

--
Daryl McCullough
Ithaca, NY

Relevant Pages

  • Re: Zenkins paper on Cantor
    ... For any total computable function l which enumerates ... Constructivism doesn't *assume* ... about the existence of "actual infinity": ... Daryl McCullough ...
    (comp.theory)
  • Re: Zenkins paper on Cantor
    ... Now, giving the list in this fashion would be potential infinity, ... note the similarity of my representation above to the fact ... that the measure of the countable reals in is 0. ... constructive in the sense of *constructivism*. ...
    (comp.theory)
  • Re: Zenkins paper on Cantor
    ... Now, giving the list in this fashion would be potential infinity, ... note the similarity of my representation above to the fact ... that the measure of the countable reals in is 0. ... constructive in the sense of *constructivism*. ...
    (sci.math)
  • Re: Uncountable many reals without Cantor
    ... Some people get strange ideas about what "constructivism" should mean. ... |debate of the "actual infinity" is so central to these matters. ... mathematics we know now to past situations. ... free-choice reals, for instance, which are free choice sequences ...
    (sci.math)
  • Re: Set Theory: Should You Believe
    ... challenging mathematics and logics foundations. ... constructivism'. ... Infinity, like zero, has no limit. ... term in this technical sense, in order to keep confusion to ...
    (sci.logic)