Re: Zenkin's paper on Cantor

From: Eray Ozkural exa (erayo_at_bilkent.edu.tr)
Date: 10/06/04 

Date: 6 Oct 2004 09:43:29 -0700

Aatu Koskensilta <aatu.koskensilta@xortec.fi> wrote in message news:<4CP8d.254$MT4.137@reader1.news.jippii.net>...
> Eray Ozkural exa from Cloud Cuckoo Land wrote:
>
> > 1. Can we take a step *after* an infinite sequence of steps in a
> > *constructivist* proof?
>
> No proof, classical or constructive, has an infinite sequence of steps.
> Perhaps this is related to your idea about integers with an infinity of
> digits?

By steps I do not necessarily mean the individual sentences in the
text of the proof (it is obvious that the proof text is finite), but
the logical steps mentioned in course of a proof. (syntax vs.
semantics) In Cantor's second proof (diagonal proof), there are
infinitely many steps, *after* which we take another step. IOW, we are
talking about a logical reasoning which is composed of infinitely many
terms, and then some. This is one of the points of Zenkin, although he
might not be able to express it eloquently. (The truth that the
transformed diagonal number is not contained in the list depends on
(the prior establishment of) infinitely many truths about individual
sentences.)

At any rate, I think that Cantor's theorem can have a finite logical
proof, but I think this will not be the diagonal proof. His first
proof is much more closer to a "proof from first principles". In fact,
the proof does not even have to be (formally) mathematical, for
continuum is precisely the "actual infinite divisibility", which can
be talked of rigorously in natural language, and likewise for "list".
I can easily state the first proof in English in a way that will leave
no doubt even for the most skeptical reader.
 
Let me repeat what it means to have a constructivist proof that "there
is a real in (0,1) that is not contained in any list 1,2,3... of
reals":
The following is a very precise presentation of the use of existential
quantifier:
http://en.wikipedia.org/wiki/Mathematical_constructivism
:To prove "for some x in X , P(a)" constructively we must present a
: particular x in X together with a proof of P(a).

In Cantor's diagonal proof, we cannot present a particular x in X with
an effective procedure.

I thought that having an effective procedure is a necessary condition
for presenting a particular x in X (for a constructivist proof!).
However, you might want to falsify me by showing a quote from Brouwer
or another champion of constructivism which argues otherwise.

If an effective procedure is not required, then constructivist
mathematics might not have much difference left from realist
mathematics. (And hence my above assumption)

Now, like Raatikainen you might think that intuitionism faces serious
problems being some sort of a logicist:
http://www.helsinki.fi/collegium/eng/Raatikainen/Intuitionism.pdf

But here we are analyzing a proof through intuitionism as originally
conceived; it is not my intent to criticize intuitionism at the
present. I am not too familiar with Dummett's views, either. It might
be the case that what I'm saying is correct in one flavor of
intuitionism, and wrong in others. Please feel free to make
corrections.

Anyway, the following mathworld page claims that proofs by
contradiction are not allowed in intuitionistic logic:
http://mathworld.wolfram.com/IntuitionisticLogic.html

Many proofs by contradiction seem valid to me from a _constructivist_
perspective (most specifically the proof of the undecidability of the
halting problem), I wonder if the above page is in error. (If so, it
might be worthwhile to warn mathworld of it for the interest of
general public)

> > 2. In general, can we say that a constructivist proof can exhibit an
> > object A by giving us a program that does *not* terminate?
>
> What does this mean?

See above.
 
> > 3. Is there the use of *actual infinity* in Cantor's diagonal proof of
> > Cantor's theorem?
>
> There's no need to appeal to "actual infinity" or what not in showing
> that there is no surjection from the naturals to the reals.

I agree with your phrase which starts with "in showing that", however,
I will not take your word for your primary claim, for which you
present absolutely no argument. Where did you hear that?

Regards, 

--
Eray Ozkural

Relevant Pages

  • Re: Zenkins paper on Cantor
    ... > No proof, classical or constructive, has an infinite sequence of steps. ... but I think this will not be the diagonal proof. ... or another champion of constructivism which argues otherwise. ... like Raatikainen you might think that intuitionism faces serious ...
    (sci.math)
  • Re: Zenkins paper on Cantor
    ... Eray "are there integers with an infinite number of digits?" ... >> No proof, classical or constructive, has an infinite sequence of steps. ... > or another champion of constructivism which argues otherwise. ... > contradiction are not allowed in intuitionistic logic: ...
    (sci.math)
  • Re: does sqrt(2) exist in CM?
    ... regardless of one's opinion on infinite sets. ... |> People have gotten the idea that constructivism has more to ... Finitistic mathematics is not ... even less basis for describing finitism as a natural part ...
    (sci.math)
  • Re: does sqrt(2) exist in CM?
    ... regardless of one's opinion on infinite sets. ... > People have gotten the idea that constructivism has more to ... > necessarily constructive, and constructive mathematics is ...
    (sci.math)
  • Re: Zenkins paper on Cantor
    ... realism and constructivism: ... of an infinite quantity as something completed is never permissible in ... (Hint: No) ... Is there the use of *actual infinity* in Cantor's diagonal proof of ...
    (comp.theory)