2
$\begingroup$

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!

Improve this question
$\endgroup$
7
  • $\begingroup$ 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 :) $\endgroup$ – nir shahar May 28 '20 at 20:56
  • $\begingroup$ 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 $\endgroup$ – Jake May 28 '20 at 22:25
  • $\begingroup$ Do you mean "Peano Arithmetic" by arithmetic dictionary? $\endgroup$ – Beleg May 28 '20 at 22:35
  • $\begingroup$ @Beleg yes, using the usual natural numbers structure for this dictionary $\endgroup$ – nir shahar May 28 '20 at 22:39
  • $\begingroup$ 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)$ $\endgroup$ – nir shahar May 28 '20 at 22:44
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$ – nir shahar May 28 '20 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.