# [FOM] Recursion Theory and Goedel's theorems

Richard Heck rgheck at brown.edu
Thu Aug 9 12:42:20 EDT 2007

```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

```