Basic arithmetic operations and bounded quantification are primitive recursive

Addition is obtained by primitive recursion from the clauses $\mathrm{add}(0,n)=n$ and $\mathrm{add}(m+1,n)=S(\mathrm{add}(m,n))$. Multiplication is then obtained by primitive recursion from $0$ and addition via $\mathrm{mul}(0,n)=0$ and $\mathrm{mul}(m+1,n)=\mathrm{add}(\mathrm{mul}(m,n),n)$. By [L1], both functions are primitive recursive.

The predecessor function is primitive recursive from $p(0)=0$ and $p(n+1)=P_1^2(n,p(n))$. Then truncated subtraction is primitive recursive by and . From this, the zero-test ${\chi }_0$ is primitive recursive via ${\chi }_0(0)=1$ and ${\chi }_0(n+1)=0$, the sign function $\mathrm{sg}(n)=1-{\chi }_0(n)$ is primitive recursive, equality is given by , and order is given by . So the listed basic arithmetic and characteristic functions are primitive recursive by [L1].

If $g:{\mathbb{N}}^{k+1}\to \mathbb{N}$ is primitive recursive, then bounded sums and products are obtained by primitive recursion through ${\mathrm{\Sigma }}_g(0,x)=g(0,x)$, ${\mathrm{\Sigma }}_g(n+1,x)={\mathrm{\Sigma }}_g(n,x)+g(n+1,x)$, ${\mathrm{\Pi }}_g(0,x)=g(0,x)$, and ${\mathrm{\Pi }}_g(n+1,x)={\mathrm{\Pi }}_g(n,x)\cdot g(n+1,x)$. Hence ${\mathrm{\Sigma }}_g$ and ${\mathrm{\Pi }}_g$ are primitive recursive by [L1].

If $r(y,x)\in \{0,1\}$ is a primitive-recursive characteristic function, then ${\chi }_{\mathrm{\exists }y\le nr(y,x)=1}(n,x)=\mathrm{sg}({\mathrm{\Sigma }}_r(n,x))$ and ${\chi }_{\mathrm{\forall }y\le nr(y,x)=1}(n,x)={\mathrm{\Pi }}_r(n,x)$. Thus bounded existential and bounded universal quantification preserve primitive recursiveness.

The displayed constructions establish every operation and quantifier listed in the statement.