In Hillary Putnam's writeup on Kripke's beautiful incompleteness proof of PA, which I learned about from Noah Schweber's answer here, I can convince myself that (see the top of p.56) "$s$ fulfills $A$" is primitive recursive in $s$, but why is $\text{Fulfills}(s, A_n)$ a primitive recursive relation in $s$ and $n$? Here $A_n$ is a fixed enumerable recursive sequence of formulas.

(I hope you find this question Noah :) )

  • $\begingroup$ (It did find me!) If I recall correctly, the point is that we basically only need an explicitly bounded search to determine whether $Fulfills(s,A_n)$ holds. Keep in mind that for every Turing machine $\Phi$ and every primitive recursive function $f$, the function sending $n$ to $\Phi(n)$ if $\Phi(n)$ halts in at most $f(n)$ stages and sending $n$ to $0$ otherwise (say) is itself primitive recursive, so you just need to check that the bound on that search is in fact appropriately small. But I don't have time at the moment to double-check this, so this is an answer as opposed to a comment. $\endgroup$ – Noah Schweber Jun 28 at 23:55
  • $\begingroup$ @NoahSchweber You mean "this is a comment as opposed to an answer"? What if I offer you 50 bounty points :) ? By the way, thanks again for all your help. I've learned A LOT from your many answers over the past months. Here and on MO. So, thank-you for that! $\endgroup$ – Jori Jun 30 at 17:28

Your Answer

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

Browse other questions tagged or ask your own question.