[FOM] Recursion Theory and Goedel's theorems
praatika@mappi.helsinki.fi
praatika at mappi.helsinki.fi
Thu Aug 9 03:30:56 EDT 2007
Arnon Avron <aa at tau.ac.il>:
> On Mon, Aug 06, 2007 at 02:06:04PM +0300, praatika at mappi.helsinki.fi
> wrote:
> > It is certainly true that recursive function theory can greatly
> > illuminate Godelian phenomena. Indeed, one cannot even formulate
> > general versions of Godel's theorem without it (as e.g. Kleene has
> > emphasized).
>
> Again, I do not think this is true. Thus the concept of a recursive
> function is not mentioned at all in Smullyan's book "Goedel's
> incompletenes theorems". He does use the notions of recursive relation
> and an r.e. set, by these are defined in purely proof-theoretical terms:
I should perhaps explain that I only meant her that the concept of
arbitrary formal system, used in the generalized version of Goedel's
theorem, depends on the (intuitive) notion of decidability. It can be
explicated and made formally exact in many different though equivalent
ways, including proof-theoretic notions such as representability, which is
indeed neat. But one always needs to lean on some version of Church-
Turing -thesis to motivate one's focus on, say, sets representable in PA
(here, that the latter coincide with intuitively decidable sets).
It is only in this sense that I meant my remark. I did not intend to
suggest that the *theory* of recursive functions, in any substantial
sense, is necessarily needed. Indeed, much of what Avron says harmonizes
with what I said.
Best, Panu
Panu Raatikainen
Ph.D., Academy Research Fellow,
Docent in Theoretical Philosophy
Department of Philosophy
University of Helsinki
Finland
E-mail: panu.raatikainen at helsinki.fi
http://www.mv.helsinki.fi/home/praatika/
More information about the FOM
mailing list