Les formules forment un ensemble primitif récursif

(i) Comme pour les termes, soit $E$ l'ensemble des formules et $E'$ celui des mots de l'une des formes annoncées, avec $\varphi, \psi \in E$. On a $E' \subset E$, puisque $E$ contient les formules atomiques et qu'il est stable par les trois règles. Inversement, $E'$ contient les formules atomiques, et il est stable par les trois règles puisque $E' \subset E$ ; d'où $E \subset E'$, par minimalité de $E$.

(ii) La relation $$\begin{aligned} \mathrm{At}(N) \iff{} &(N)^0 = 0 \wedge \exists j < l\ \big(j \geqslant 2 \\ &\wedge \mathrm{Tm}(\mathrm{sm}(N, 1, j)) \\ &\wedge \mathrm{Tm}(\mathrm{sm}(N, j, l))\big), \end{aligned}$$ où $l = \mathrm{lg}(N)$, traduit la définition, et elle est primitive récursive par Termes et Clôture.

Pour $\mathrm{Fm}$, soit $Q(N, h)$ la disjonction de quatre conditions, où $l = \mathrm{lg}(N)$ :

$\mathrm{At}(N)$ ;

$(N)^0 = 1$, $l \geqslant 2$ et $(h)^{\mathrm{sm}(N, 1, l)} = 1$ ;

$(N)^0 = 2$, et il existe $j < l$ tel que $j \geqslant 2$, $(h)^{\mathrm{sm}(N, 1, j)} = 1$ et $(h)^{\mathrm{sm}(N, j, l)} = 1$ ;

$(N)^0 = 3$, $l \geqslant 3$, $(N)^1 \geqslant 8$ et $(h)^{\mathrm{sm}(N, 2, l)} = 1$.

Elle est primitive récursive, et la récurrence de valeurs fournit une relation primitive récursive $R$ telle que $R(N) \iff Q(N, \bar\chi_R(N))$. Les codes consultés sont ceux de facteurs qui omettent la première lettre, plus petits que $N$ ; la même récurrence forte que pour les termes, appuyée sur (i), montre que $R = \mathrm{Fm}$.

(iii) La fonction $\mathrm{dec}$ est primitive récursive par la minimisation bornée (Clôture, (iv)). Si $N$ code ${\to}\, \varphi\, \psi$, l'entier $j_0 = 1 + \mathrm{lg}(\ulcorner \varphi \urcorner)$ vérifie la condition, et $j_0 < \mathrm{lg}(N)$ puisque $\psi$ n'est pas vide.

Si un entier $j$ la vérifie, le mot de code $N$ s'écrit ${\to}\, \varphi'\, \psi'$, où $\varphi'$ et $\psi'$ sont les formules de codes $\mathrm{sm}(N, 1, j)$ et $\mathrm{sm}(N, j, \mathrm{lg}(N))$. Le théorème de lecture unique donne $\varphi' = \varphi$, donc $j = j_0$. Ainsi $\mathrm{dec}(N) = j_0$, et les deux facteurs sont $\varphi$ et $\psi$.