# 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 :) May 28 '20 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 '20 at 22:25
• Do you mean "Peano Arithmetic" by arithmetic dictionary? May 28 '20 at 22:35
• @Beleg yes, using the usual natural numbers structure for this dictionary May 28 '20 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)$ May 28 '20 at 22:44

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'.