Substitution of Constant yields Primitive Recursive Function

Theorem

Let $f: \N^{k + 1} \to \N$ be a primitive recursive function‎.

Then $g: \N^k \to \N$ given by:

$\map g {n_1, n_2, \ldots, n_k} = \map f {n_1, n_2, \ldots, n_{i - 1}, a, n_i \ldots, n_k}$

is primitive recursive.

Proof

Let $n = \tuple {n_1, n_2, \ldots, n_{i - 1}, n_i \ldots, n_k}$.

We see that:

$\map g {n_1, n_2, \ldots, n_k} = \map f {\map {\pr^k_1} n, \map {\pr^k_2} n, \ldots, \map {\pr^k_{i - 1} } n, \map {f_a} n, \map {\pr^k_i} n, \ldots, \map {\pr^k_k} n}$

We have that:

• $\pr^k_j$ is a basic primitive recursive‎ function for all $j$ such that $1 \ne j \le k$
• $f_a$ is a primitive recursive‎ function.

So $g$ is obtained by substitution from primitive recursive‎ functions and so is primitive recursive‎.

$\blacksquare$