Les termes forment un ensemble primitif récursif

(i) Soit $E$ l'ensemble des termes et $E'$ l'ensemble des mots de l'une des formes annoncées, avec $t, u \in E$. Comme $E$ contient les variables et $0$ et qu'il est stable par les trois symboles de fonctions, $E' \subset E$.

Inversement, $E'$ contient les variables et $0$. Il est stable : si $t$ et $u$ sont dans $E'$, ils sont dans $E$, et $S\, t$, $+\, t\, u$, $\times\, t\, u$ sont dans $E'$ par définition. Comme $E$ est le plus petit ensemble qui a ces propriétés, $E \subset E'$.

(ii) On a $\mathrm{Var}(N) \iff \mathrm{lg}(N) = 1 \wedge (N)^0 \geqslant 8$, relation primitive récursive par Clôture, (i), et Codages.

Pour $\mathrm{Tm}$, soit $Q(N, h)$ la disjonction des trois conditions suivantes, où $l = \mathrm{lg}(N)$ :

$l = 1$, et $(N)^0 = 4$ ou $(N)^0 \geqslant 8$ ;

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

$(N)^0 = 6$ ou $(N)^0 = 7$, 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$.

C'est une relation primitive récursive par les points (i) et (iii) de Clôture, la quantification étant bornée par $\mathrm{lg}(N)$. La récurrence de valeurs, (ii), fournit une relation primitive récursive $R$ telle que $R(N) \iff Q(N, \bar\chi_R(N))$.

Montrons par récurrence forte sur $N$ que $R(N)$ si et seulement si $N$ code un terme. Les entiers $\mathrm{sm}(N, 1, l)$, $\mathrm{sm}(N, 1, j)$ et $\mathrm{sm}(N, j, l)$ qui interviennent, avec $1 \leqslant j \leqslant l$, codent des facteurs qui omettent la première lettre ; ils sont strictement plus petits que $N$ par le point (ii) du codage des mots. Pour un tel entier $M$, on a donc $(\bar\chi_R(N))^M = \chi_R(M)$, qui vaut $1$ si et seulement si $M$ code un terme, par hypothèse de récurrence.

Ainsi $Q(N, \bar\chi_R(N))$ dit que le mot de code $N$ est une variable ou $0$, ou bien $S$ suivi d'un terme, ou bien $+$ ou $\times$ suivi d'un mot qui se coupe en deux termes non vides, le premier occupant les rangs $1$ à $j - 1$ et le second les rangs $j$ à $l - 1$. Par (i), c'est dire que $N$ code un terme : $R = \mathrm{Tm}$.