Proposition 1Arithmétisation de la syntaxe

Codage des mots du langage de l'arithmétique

Le langage de l'arithmétique a pour signature une constante $0$ , un symbole de fonction unaire $S$ et deux symboles de fonctions binaires $+$ et $\times$ (Langage, signature). On énumère son alphabet par $\begin{aligned} &a_0 = {=},\ a_1 = \neg,\ a_2 = {\to},\ a_3 = \forall, \\ &a_4 = 0,\ a_5 = S,\ a_6 = +,\ a_7 = \times, \end{aligned}$ puis $a_{8+i} = x_i$ pour les variables : la lettre $a_k$ est une variable si et seulement si $k \geqslant 8$ .

Le code d'un mot $w = a_{k_0} \cdots a_{k_{m-1}}$ est l'entier $\ulcorner w \urcorner = \langle k_0, \dots, k_{m-1} \rangle$ , codage du point (iii) de l'extension par témoins, repris dans Codages. Tout entier est le code d'une unique suite finie d'entiers, donc d'un unique mot ; on parle du « mot de code $N$ », dont la lettre de rang $j$ est $a_{(N)^j}$ pour $j < \mathrm{lg}(N)$ .

Un facteur d'un mot $w$ est un mot formé de lettres consécutives de $w$ , c'est-à-dire un mot $u$ tel que $w = vuv'$ pour des mots $v$ et $v'$ , éventuellement vides. On note $\mathrm{sm}(N, i, j)$ le code du facteur $(N)^i \cdots (N)^{j-1}$ , formé des lettres de rangs $i$ à $j - 1$ , pour $i \leqslant j \leqslant \mathrm{lg}(N)$ .

Enfin, $\mathrm{cc}(M_1, \dots, M_r)$ désigne le code de la concaténation des mots de codes $M_1, \dots, M_r$ , obtenu par $r - 1$ concaténations successives : $\begin{aligned} &\mathrm{cc}(M_1, \dots, M_r) \\ &\quad = \mathrm{conc}\big(\mathrm{cc}(M_1, \dots, M_{r-1}), M_r\big). \end{aligned}$

Énoncé

(i) Les fonctions $\mathrm{sm}$ et $\mathrm{cc}$ sont primitives récursives, de même que $k \mapsto \langle c_1, \dots, c_r, k \rangle$ pour des entiers $c_1, \dots, c_r$ fixés.

(ii) Facteurs. Si $u$ est un facteur de $w$ , alors $\ulcorner u \urcorner \leqslant \ulcorner w \urcorner$ , et l'inégalité est stricte si $u \neq w$ . En particulier, $\mathrm{sm}(N, i, j) < N$ dès que $i \leqslant j \leqslant \mathrm{lg}(N)$ et que $i \geqslant 1$ ou $j < \mathrm{lg}(N)$ .

(iii) Si la lettre $a_k$ figure dans le mot de code $N$ , alors $2k + 1 \leqslant N$ , donc $k < N$ .

Démonstration

(i) Définissons, par récurrence primitive sur $t$ , avec les paramètres $N$ et $i$ , $\begin{aligned} \sigma(N, i, 0) &= 0, \\ \sigma(N, i, t + 1) &= \mathrm{aj}\big(\sigma(N, i, t),\ (N)^{i+t}\big). \end{aligned}$ Par récurrence sur $t$ , $\sigma(N, i, t)$ code la suite $(N)^i, \dots, (N)^{i+t-1}$ ; on pose $\mathrm{sm}(N, i, j) = \sigma(N, i, j \mathbin{\dot{-}} i)$ . La fonction $\mathrm{cc}$ est une composée de $\mathrm{conc}$ , et $\langle c_1, \dots, c_r, k \rangle = \mathrm{aj}(\mathrm{aj}(\cdots\mathrm{aj}(0, c_1) \cdots, c_r), k)$ ; toutes sont primitives récursives par Codages, (iii).

(ii) Préfixes. Pour un mot $w$ et une lettre $a_k$ , on a $\ulcorner w\, a_k \urcorner = 2^{\ulcorner w \urcorner}(2k + 1) > \ulcorner w \urcorner,$ puisque $2^n > n$ pour tout entier $n$ . Par récurrence sur la longueur de $v$ , il vient $\ulcorner u \urcorner < \ulcorner u v \urcorner$ si $v$ n'est pas vide.

Suffixes. Montrons $\ulcorner v \urcorner \leqslant \ulcorner u v \urcorner$ , avec inégalité stricte si $u$ n'est pas vide, par récurrence sur la longueur de $v$ . Si $v$ est vide, $\ulcorner v \urcorner = 0$ , et le code d'un mot non vide, de la forme $2^n(2k + 1)$ , est au moins $1$ . Si $v = v' a_k$ , l'hypothèse de récurrence et la croissance stricte de $n \mapsto 2^n$ donnent $\begin{aligned} \ulcorner v' a_k \urcorner &= 2^{\ulcorner v' \urcorner}(2k + 1) \\ &\leqslant 2^{\ulcorner u v' \urcorner}(2k + 1) = \ulcorner u v' a_k \urcorner, \end{aligned}$ avec inégalité stricte si l'hypothèse l'est.

Si enfin $w = v u v'$ , on a $\ulcorner u \urcorner \leqslant \ulcorner v u \urcorner \leqslant \ulcorner v u v' \urcorner$ , et si $u \neq w$ , l'un des mots $v$ et $v'$ n'est pas vide, ce qui rend stricte l'une des deux inégalités. Le facteur de code $\mathrm{sm}(N, i, j)$ est différent du mot de code $N$ si $i \geqslant 1$ ou $j < \mathrm{lg}(N)$ , puisqu'il est alors plus court.

(iii) Le mot $a_k$ , réduit à une lettre, est un facteur du mot de code $N$ , et son code est $\langle k \rangle = 2^0(2k + 1)$ ; on applique (ii).

□

Remarque

Les premiers codes restent lisibles : $\ulcorner 0 \urcorner = \langle 4 \rangle = 9$ , $\ulcorner x_0 \urcorner = 17$ , puis $\ulcorner S\, 0 \urcorner = 2^{\ulcorner S \urcorner} \cdot 9 = 2^{11} \cdot 9 = 18\,432,$ et $\ulcorner {=}\, x_0\, 0 \urcorner = 2^{34} \cdot 9 = 154\,618\,822\,656$ , puisque $\ulcorner {=}\, x_0 \urcorner = 2^1 \cdot 17 = 34$ . Mais dès cinq lettres, le code de $\forall x_0\, (x_0 = x_0)$ est une tour d'exponentielles dont le premier étage, $2^{2176}$ , a déjà $656$ chiffres. Seules comptent ici l'existence de ces entiers et les inégalités du point (ii).

Remarque

Le code ne croît pas avec la longueur : $\ulcorner x_{10000} \urcorner = 20\,017$ dépasse $\ulcorner S\, 0 \urcorner = 18\,432$ , alors que le premier mot n'a qu'une lettre. Le point (ii) ne compare que des mots dont l'un est facteur de l'autre, et c'est exactement ce dont la récurrence de valeurs a besoin : un mot se reconnaît à partir de ses facteurs propres, qui ont des codes plus petits.

Repose sur

Fonctions primitives récursives

Sert à

Les termes forment un ensemble primitif récursif