# Expressing functions using the arithmetic dictionary

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!

• Im unsure if this question was asked already in a similar forum. If it was, i will gladly take the question down and look at the answer there :) – nir shahar May 28 at 20:56
• Can you define the elements of that "dictionary"? I suspect that the general recursive functions is what you're basically looking for: en.wikipedia.org/wiki/General_recursive_function – Jake May 28 at 22:25
• Do you mean "Peano Arithmetic" by arithmetic dictionary? – Beleg May 28 at 22:35
• @Beleg yes, using the usual natural numbers structure for this dictionary – nir shahar May 28 at 22:39
• To clarify, when i said "can be expressed by the arithmetic dictionary" i meant that there exists a first order logic formula $\phi (z)$ such that $f(x) = y$ if and only if $\phi (y)$ – nir shahar May 28 at 22:44

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.

• you are right that this is not exactly what i need (and in fact, we have not even started defining provability under PA for first order logic) although, this seems to be very similar to my question so i will take a look at that. Thanks! – nir shahar May 28 at 23:02