[FOM] Re: Comment on Church's Thesis (Harvey Friedman)

Vladimir Sazonov V.Sazonov at csc.liv.ac.uk
Mon Jan 12 14:13:51 EST 2004

Alexander Zenkin wrote:
> -----Original Message-----
> From: fom-bounces at cs.nyu.edu [mailto:fom-bounces at cs.nyu.edu]On Behalf Of
> Vladimir Sazonov
> Sent: Wednesday, January 07, 2004 9:28 PM
> To: addamo
> Cc: FOM
> Subject: Re: [FOM] Re: Comment on Church's Thesis (Harvey Friedman)
> addamo wrote:
> >
> > I don't understand how your comment refers to Church's Thesis.
> > Could you make it more explicit?
> >
> > Do you or anybody know a proof of the undecidability of the Halting
> problem
> > not depending on Church's Thesis?
> Sorry, how is it possible that any mathematical theorem (such as
> the undecidability of the Halting problem) may depend on anything
> what is not a mathematical theorem or axiom (like Church's Thesis
> which is not a mathematical statement)?
> Of course, the intuitive meaning of a theorem may depend on some
> intuitive (informal) considerations. 
> [. . .]
> Vladimir Sazonov
>         Solomon Feferman writes in one place, "The ideas of potential vs. actual
> infinity are vague but at the intuitive, philosophical level very
> suggestive."

I completely agree both with vagueness and philosophical value.

>         Wilfried Hodges writes in one place: " . . .the author observes quite
> correctly that the PROOF of Cantor's theorem (on the uncountability of the
> real line) depends on acceptance of actual infinity."
>         How is it possible that not simply mathematical theorem (Cantor's theorem
> on the uncountability of continuum), not "the intuitive meaning of the
> theorem", but its MATHEMATICAL PROOF may depend on an acceptance of the
> "vague, intuitive, philosophical" notion of "actual infinity" "what is
> <certainly> not a mathematical theorem or axiom"?

I do not know the proper context of the above citation of 
Wilfried Hodges. But I understand it that the very formulation 
and the proof of Cantor's theorem may be considered (mathematically) 
only with acceptance of the infinity axiom in set theory  
(together with powerset axiom). This acceptance is related with 
acceptance of actual infinity. (By the way, the same person may 
accept this in one case and, in another considerations, may 
reject this as well.) Also while proving Cantor's theorem or 
anything else, we usually consider this proof not only formally, 
but also intuitively. ONLY in this way we use actual infinity 
or other vague ideas in mathematical proofs. I see here no 

Of course, there is another, generalized version of Cantor's 
theorem that powerset of any set X (finite or infinite) is not 
in bijectibve correspondence to X. Essentially the same 
diagonal method works quite independently on infinity (axiom 
or, informally, on actual infinity). This seems has a relation 
to another (interesting) posting of Andrew Boucher. (I also 
sometimes prefer to consider arithmetic with the biggest 
natural number with a different goal). 

Sorry, I did not say here anything essentially new. 
This is just a reply, once a question was stated. 

Vladimir Sazonov

>         Alexander Zenkin

More information about the FOM mailing list