[FOM] Recursion Theory and Goedel's theorems

[Arnon Avron]

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:
an r.e. set is a set which is defined by a formula of the form
\exists x A, where A is a formula in the language of PA in which
all quantifiers are bounded. 

  An even better (in my opinion) general formulation can be given
if instead of using the natural numbers as the framework for encoding
syntax one follows Feferman's recommendation and uses instead the
much more natural (for the task of encoding) set V_0 of S-expressions
(i.e. the least set which contains 0 and is closed under the pairing
function (_,_)). A subset of V_0 is r.e. iff it is definable by a formula
of the language PTC+, where the later is defined as follows:

Terms:
------

1) The constant 0 is a term.
2) Every (individual) variable is a term.
3) If t and s are terms then so is (t,s).

Formulas
========

1) If t and s are terms then t=s is a formula.
2) If A and B are formulas then so are their disjunction and
   conjunction.
3) If A is a formula, x,y are two different variables,
   and t,s are terms, then (TC_{x,y}A)(t,s) is a formula.

  (Here TC_{x,y}A) expresses the non-reflexive transitive closure
   of the the binary relation between x and y expresses by A).

One general formulation of Goedel's first theorem is: "Every consistent
extension of PA whose set of theorems is definable by a formula
of PTC+ is incomplete" (other versions can similarly be formulated).

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.

Arnon Avron