Closure properties of primitive recursive functions

A general recursive function that can be constructed without using minimization is called primitive recursive. Let the functions $g$ and $f$ be primitive recursive, $h=\mu g$, $h$ — a general recursive function, and let $h$ be majorized by the function $f: h(\bar{x})<f(\bar{x})$ for all $\bar{x}$. Prove that $h$ is also primitive recursive.

We say that the function $h^{(n+1)}$ is obtained by bounded minimization of the function $f^{(n+1)}$ (denoted $h=\mu_{\lim } f$), if $h(\bar{x}, y)=y$, when $f(\bar{x}, y) \neq 0$ for all $z<y$, and otherwise $h(\bar{x}, y)$ equals the smallest $z<y$ for which $f(\bar{x}, z)=0$. Prove that the function $\mu_{\lim } f$ can be constructed from $f$ and the basis functions by means of superposition and primitive recursion. $\circledast$

A g.r.f. that can be constructed without using minimization is called primitively recursive. Let the functions $g$ and $f$ be primitively recursive, $h=\mu g$, $h$ a g.r.f., and let $h$ be majorized by the function $f: h(\bar{x})<f(\bar{x})$ for all $\bar{x}$. Prove that $h$ is also primitively recursive. $\circledast$

Assume that $R: \mathbf{N}^{k+1} \rightarrow \mathbf{N}$ is a primitive recursive predicate. Show that the following function $f: \mathbf{N}^{k+1} \rightarrow \mathbf{N}$ is also primitive recursive:

Assume that $f: \mathbf{N}^{k+1} \rightarrow \mathbf{N}$ is primitive recursive. Show that the following functions are also primitive recursive:

Assume that both $f: \mathbf{N} \rightarrow \mathbf{N}$ and $g: \mathbf{N} \rightarrow \mathbf{N}$ are primitive recursive. Show that the following function $h: \mathbf{N}^{2} \rightarrow \mathbf{N}$ is also primitive recursive:

Assume that $f: \mathbf{N} \rightarrow \mathbf{N}$ is primitive recursive. Show that the following function $g: \mathbf{N}^{2} \rightarrow \mathbf{N}$ is also primitive recursive:

Show that every context-free language is primitive recursive.

Assume that $f: \mathbf{N} \rightarrow \mathbf{N}$ is primitive recursive. Then, the function $g: \mathbf{N}^{2} \rightarrow \mathbf{N}$, defined by

is also primitive recursive.

Prove that every primitive recursive function is everywhere defined.

Prove that if the function $f^{n}(x_{1}, \ldots , x_{n})$ is primitive recursive, then the following functions are primitive recursive:

Which functions are obtained from the simplest functions using superpositions alone?

Prove that the functions $x+1$ and $2x$ cannot be obtained from $o^{1}$ and $I_{m}^{n}$ using superpositions and primitive recursion schemes.

Let $g^{n+1}, \alpha^{m}, \beta^{m}$ be primitive recursive functions. Prove that the following functions are primitive recursive:

Prove that if $f$ is obtained from primitive recursive functions $g$ and $h$ by means of the bounded $\mu$-operator, then $f$ is primitive recursive.

Let the functions $f_{0}^{n}, f_{1}^{n}, \ldots , f_{s}^{n}$ have the following property: for any natural values $x_{1}, \ldots , x_{n}$, one and only one of these functions equals $0$. We say that the function $g^{n}$ is defined by cases, if

Prove that if the functions $h_{0}^{n}, \ldots , h_{s}^{n}, f_{0}^{n}, \ldots , f_{s}^{n}$ are primitive recursive, then $g^{n}$ is primitive recursive.

Prove that if the functions $g, h, t_{1}, \ldots , t_{s}$ are primitive recursive and $f$ is obtained from them by course-of-values recursion with delays, then the function $f$ is primitive recursive.

Let the functions $f$ and $g$ be defined as follows:

Prove that if the functions $h_{1}$ and $h_{2}$ are primitive recursive, then the functions $f$ and $g$ are primitive recursive.

Let $f_{1}^{n+1}, \ldots , f_{k}^{n+1}$ be defined by means of simultaneous recursion:

for all $1 \leq i \leq k$.

Prove that if the functions $g_{1}, \ldots , g_{k}, h_{1}, \ldots , h_{k}$ are primitive recursive, then the functions $f_{1}, \ldots , f_{k}$ are primitive recursive.

Prove that every primitive recursive function is general recursive.