# Gödel Incompleteness Theorem - Primitive Recursive Functions

I'm currently studying Gödel's Incompleteness Theorem and I am in doubt about his use of primitive recursive functions.

To study it, i'm in the point of view of a system of predicate logic with the theory of Peano Arithmetic. That predicate logic has the extensions of equality (symbol $=$ defined) and function symbols.

1) In Gödel's proof he defines in some point the primitive recursive functions. Those definitions are necessary even if i'm using the function symbols extensions for predicate logic? The function symbols already offer an way of composing functions. An function $f \in F$ has the form of $f(t_1, t_2, \dotsc, t_n)$ where $t_n$ is any term of the logical system. But a function $f$ represents a term too. So we can compose functions like in $f(g(x))$ where $t_1=g(x)$. I don't see where the primitive recursion rule would give some benefit.

2) Another doubt is whether the primitive recursive functions is in the syntax domain or in the semantics domain. If in the semantic domain, how can I use expressions from inside the logical system? For example, in defining those functions i use the concepts $\forall$, $\exists$, $\land$ and the like.

3) At some point in the proof, he introduces the representability concept. It afirms that any definable relation can be expressed as a formula of the system. Why is this used for?

Thank you in advance.

• Representability shows that (among others) the primitive recursive functions have analogues within the system. This is part of what makes it possible for the system to "talk about itself" (via indexing). – André Nicolas May 25 '12 at 14:46

What this is used for is to connect "correct proof" at the metalevel with a property in the formal system. Gödel proves that "$x$ is (the Gödel number of) a valid proof of formula $y$" is a primitive recursive property, and therefore there is a formula in the system itself that is provable exactly when you plug in numerals for Gödel numbers of valid proofs. This is the core of the construction of an undecidable sentence.