 Theorem 3.9  can be demonstrated by first observing that the truth of a \(\Sigma^0_1\)-formula \(\varphi^k_e(\vec{x})\) is equivalent to \(\mathfrak{N} \models \psi^k_e(n,\vec{m})\) for some \(n \in \mathbb{N}\). Next note that the sequence of observations recorded in  Section 2.1.2  suffices to show that all \(\Delta^0_0\)-definable relations are primitive recursive. We may thus consider an algorithm which on input \(e,\vec{m}\) uses \(e\) to construct \(\psi^k_e(x,\vec{y})\) and then performs an unbounded search for an \(n\) such that \(\psi^k_e(n,\vec{m})\) holds. By an appeal to Church’s Thesis (which can, of course, be replaced by an explicit construction) there is a computable function \(f(e)\) for which we have the following: 