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