Propriétés de clôture des fonctions primitives récursives

(i) On a $$\chi_=(x, y) = \overline{\mathrm{sg}}\big((x \mathbin{\dot{-}} y) + (y \mathbin{\dot{-}} x)\big),$$ puis $\chi_<(x, y) = \mathrm{sg}(y \mathbin{\dot{-}} x)$ et $\chi_\leqslant(x, y) = \overline{\mathrm{sg}}(x \mathbin{\dot{-}} y)$, toutes composées des exemples de Primitives récursives.

Ensuite $\chi_{\neg R} = 1 \mathbin{\dot{-}} \chi_R$, $\chi_{R \wedge R'} = \chi_R \cdot \chi_{R'}$ et $\chi_{R \vee R'} = \mathrm{sg}(\chi_R + \chi_{R'})$. La substitution des $g_j$ est une composition.

(ii) La fonction cherchée est $\sum_{i=1}^{k} g_i \cdot \chi_{R_i}$, puisqu'en chaque point exactement un des $\chi_{R_i}$ vaut $1$ ; c'est une composée d'additions et de multiplications.

(iii) La somme $s(x, y)$ vérifie $s(x, 0) = 0$ et $s(x, y + 1) = s(x, y) + f(x, y)$ : c'est une récurrence primitive. Le produit se traite de même, avec la valeur initiale $1$. Enfin $$\chi_{\exists z < y\, R}(x, y) = \mathrm{sg}\Big(\sum_{z < y} \chi_R(x, z)\Big),$$ et $\chi_{\forall z < y\, R}(x, y) = \prod_{z < y} \chi_R(x, z)$.

(iv) Soit $z_0$ le plus petit $z$ tel que $R(x, z)$, s'il existe. Le produit $\prod_{z \leqslant t} \big(1 \mathbin{\dot{-}} \chi_R(x, z)\big)$ vaut $1$ si $t < z_0$, ou si $z_0$ n'existe pas, et $0$ sinon. La somme de ces produits pour $t < y$ compte les $t < y$ inférieurs à $z_0$ : $$\begin{aligned} &\mu z < y\, R(x, z) \\ &\quad = \sum_{t < y}\ \prod_{z < t + 1} \big(1 \mathbin{\dot{-}} \chi_R(x, z)\big), \end{aligned}$$ qui vaut $z_0$ si $z_0 < y$, et $y$ sinon. C'est une fonction primitive récursive par (iii).

(v) Pour $d \geqslant 1$, le quotient de $x$ par $d$ est le plus petit $q$ tel que $d(q + 1) > x$, et il est au plus $x$ puisque $d(x + 1) > x$. Ainsi $$q(x, d) = \mu q < x + 1\, \big(d(q + 1) > x\big),$$ formule qui donne aussi $q(x, 0) = x + 1$, et $r(x, d) = x \mathbin{\dot{-}} d \cdot q(x, d)$. L'unicité de la division euclidienne (Division euclidienne) garantit que ce sont bien le quotient et le reste.

Enfin $d \mid x$ équivaut à $\exists k < x + 1\ (dk = x)$, et $x$ est premier si et seulement si $x \geqslant 2$ et $\forall d < x\, \big(d \leqslant 1 \vee \neg(d \mid x)\big)$ ; on conclut par (i) et (iii).