Theorem 2.2.10. Assuming that:

$f : ℕ^{k} \to ℕ$ a partial function

Then

f

is recursive if and only if there is a

Σ_{1}

-formula

𝜃 (\bar{x}, y)

such that

y = f (\bar{x}) ⟺ ℕ ⊨ 𝜃 (\bar{x}, y)

.