Expressing functions using the arithmetic dictionary

Question

i have seen in the "logic to cs" class i take - a theorem that states: "every recursive (computable) function $f$ can be expressed using the arithmetic dictionary {$C_0, C_1, f_+(,), f_x(,), R_\le(,)$} with the structure {$D=\mathbb{N} ,C_0=0,C_1=1, f_+(a,b) =a+b, f_x(a,b)=ab, R_\le(a,b) = a\le b $}"

But we didnt prove this theorem because a part of the students didnt take the "computational models" course (i did take it though)

Where can i find a proof for this theorem? Thanks in advance!

Answer 1

I'm not sure this is exactly what you are looking for, but you might find what you want in Theorem 3.2.1 of Computability Theory by S. Barry Cooper:

All recursive functions are representable in PA.

that is for any recursive function $f$, there exists a binary predicate $F$ in the language of arithmetic such that for any natural numbers $x$ and $y$ we have $$ f(x) = y ~\Rightarrow~ \vdash_{PA} F(x,y) $$ and $$ f(x) \neq y ~\Rightarrow~ \vdash_{PA} \lnot F(x,y) $$ where $\vdash_{PA}$ means 'PA proves'.

This theorem is central to Gödel's famous incompleteness theorem, so you might also want to take a look at ch. 8 of the mentioned book where it is discussed, and this notion of 'representability' is extended to 'semi-representability', to include the c.e. sets as well.