[FOM] Recursion Theory and Goedel's theorems

[Richard Heck]

Arnon Avron wrote:
> Now I am not denying that Goedel's first theorem *can* be described
> mainly (but not solely!) in recursive theoretic terms, or even that
> recursion theory shed some light on the incompleness phenomenon
> (though I dont think that it really provides significant insight
> into it). However, I do claim that it is not necessary to do so.
> Goedel theorems are about axiomtic theories, syntax,
> and  provability (and perhaps also truth). There is no way to formulate 
> or understand them without these notions. On the other hand it is possible 
> to formulate them (in the most general forms), prove them
> and understand them without knowing anything about recursion theory.
>   
This may be true, but I am not sure that the INTEREST of the theorem is 
clear without the connection to notions from recursion theory. Who cares 
if a set is definable by a formula from PTC+? The fact that such sets 
are exactly the r.e. sets explains why we should care---though, even 
then, I think one needs also to know that the set of theorems of a 
system is r.e. iff it is recursively axiomatizable. If that were not so, 
it seems to me, then systems whose theorems are r.e. would not be of 
much interest. In that sense, I think Goedel's original formulation is 
the one that explains why the theorem has the interest it does: Every 
system whose set of axioms is general recursive etc, etc. But even then 
remember Goedel's footnote to the whenever reprinting, saying how it is 
only after Turing's work that a fully satisfactory statement of the 
theorem became possible. This is despite the fact that, of course, a set 
is Turing computable iff it is general recursive. In Goedel's view, that 
is, the notion of interest was that of a system whose set of axioms is 
computable---and of course that turns out to be equivalent, 
mathematically---though not, my point is, conceptually---to a system 
whose set of theorems is r.e. let alone definable in PTC+.

Richard

-- 
==================================================================
Richard G Heck, Jr
Professor of Philosophy
Brown University
http://frege.brown.edu/heck/
==================================================================
Get my public key from http://sks.keyserver.penguin.de
Hash: 0x1DE91F1E66FFBDEC
Learn how to sign your email using Thunderbird and GnuPG at:
http://dudu.dyn.2-h.org/nist/gpg-enigmail-howto