Why are all computable functions representable in PA?

Question

I'm trying to understand the proof of the first incompleteness theorem, and more specifically, the diagonal lemma. Suppose $GN(x)$ is the Gödel Number of a formula $x$.

The first step of the diagonal lemma, as I understand it, is to let $f:\mathbb{N}\rightarrow\mathbb{N}$ be such that $f(GN(\phi))=GN(\phi(GN(\phi)))$ where $\phi$ is any formula with one free variable, and $f(a)=0$ when $a \neq GN(\phi)$ for any formula with one free variable $\phi$.

I need to show that such a function is representable in PA, or in other words, that there exists a formula with two free variables $\psi$ such that $f(x)=y\leftrightarrow PA\vdash \psi(x,y)$. I understand why the function is computable, so what I need to do is show that all computable functions are representable in PA. Any hint or proof sketch would be really useful.

Answer 1

Here is (a sketch of) one route. Let $\mathfrak{N}$ denote the standard model of arithmetic.

Begin by showing that all r.e. relations are definable by $\Sigma^0_1$ formulas in $\mathfrak{N}$. There are a few ways to do this, depending on which computational model you wish to start from. One interesting way is to show that given a fixed Turing machine $M$, the set $\{x \mid M(x) \text{ halts}\}$ is $\Sigma^0_1$. The proof involves representing the computation of $M$ on a given input by a "tableau" (a square matrix of natural numbers whose rows represent configurations of $M$ at each step of the computation), and asserting the existence (using the Gödel beta function) of such a tableau. Its correctness (the fact that it corresponds to an actual computation of $M$) can be ensured by asserting that each 2x3 submatrix of the tableau is correct. Sipser's textbook contains more details on the tableau method. Alternatively, one can use induction on the calculus of $\mu$-recursive functions (see Enderton) or register machines (Ebbinghaus, Flum, and Thomas).

The next step would be to show that $\mathrm{PA}$ "allows representations": if $\theta$ is any $\Sigma^0_1$ sentence such that $\mathfrak{N} \vDash \theta$, then $\mathrm{PA} \vdash \theta$. Since the graph of a recursive function is an r.e. relation, and hence defined by a $\Sigma^0_1$ formula in $\mathfrak{N}$, what you require follows. To prove that $\mathrm{PA}$ allows representations, begin by showing that it can prove the true bounded (or $\Delta_0$) sentences in the language of arithmetic with $\le$. This can be shown by induction on the complexity of the $\Delta_0$ sentence. The corresponding fact for $\Sigma^0_1$ sentences follows immediately.