[FOM] Recursion Theory and Goedel's theorems

[praatika@mappi.helsinki.fi]

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/