Composition and primitive recursion as closure schemes on arithmetic functions

Let $g:{\mathbb{N}}^m\to \mathbb{N}$ and let $h_1,\dots ,h_m:{\mathbb{N}}^k\to \mathbb{N}$ be total arithmetic functions. Their composition is the function $x⟼g(h_1(x),\dots ,h_m(x))$ from ${\mathbb{N}}^k$ to $\mathbb{N}$.

Let $g:{\mathbb{N}}^k\to \mathbb{N}$ and $h:{\mathbb{N}}^{k+2}\to \mathbb{N}$ be total arithmetic functions. A function $f:{\mathbb{N}}^{k+1}\to \mathbb{N}$ is obtained from $g$ and $h$ by primitive recursion when $f(0,x_1,\dots ,x_k)=g(x_1,\dots ,x_k)$ and $f(n+1,x_1,\dots ,x_k)=h(n,f(n,x_1,\dots ,x_k),x_1,\dots ,x_k)$ for every $n\in \mathbb{N}$ and every $x_1,\dots ,x_k\in \mathbb{N}$.

By The recursion theorem, once $g$ and $h$ are fixed there exists a unique total function $f$ satisfying these two clauses.

• Composition does not change totality.

• Primitive recursion is recursion on one distinguished natural-number argument, with the previous function value available in the recursive clause.