Primitive recursive function

Definition

The class of primitive recursive functions is the smallest class of functions $f \colon \N^k \to \N$, for $k \ge 0$, with the following properties.

1. It contains the constant function $0$ of arity $0$, and the successor function $S(x) = x + 1$.
2. It contains the projections $P^k_i(x_1, \ldots, x_k) = x_i$ for $1 \le i \le k$.
3. It is closed under composition: if $g \colon \N^m \to \N$ and $h_1, \ldots, h_m \colon \N^k \to \N$ are in the class, so is $\bar x \mapsto g(h_1(\bar x), \ldots, h_m(\bar x))$.
4. It is closed under primitive recursion: if $g \colon \N^k \to \N$ and $h \colon \N^{k+2} \to \N$ are in the class, so is the function $f \colon \N^{k+1} \to \N$ given below.

$$f(0, \bar x) = g(\bar x), \qquad f(y + 1, \bar x) = h(y, f(y, \bar x), \bar x).$$

Here $\N = \set{0, 1, 2, \ldots}$ is the set of natural numbers.