Re: Zenkin's paper on Cantor

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

  • Next message: David C. Ullrich: "Re: Zenkin's paper on Cantor" 
    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
  • Next message: David C. Ullrich: "Re: Zenkin's paper on Cantor"

    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 ...
      (sci.math)
    • 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)
    Loading