# Kripke's proof of the incompleteness of PA

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 :) )

• (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. – Noah Schweber Jun 28 at 23:55
• @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! – Jori Jun 30 at 17:28