Les ensembles récursivement énumérables sont définissables dans ℕ

(i) Changement de variables. Soit $A$ défini par $\varphi$ et $v_1, \dots, v_n$, et soit $w_1, \dots, w_m$ des variables distinctes qui ne figurent pas dans $\varphi$ et sont distinctes de $v_1, \dots, v_n$. La formule $$\begin{aligned} &\exists v_1 \cdots \exists v_n\, \big(v_1 = w_{\alpha(1)} \wedge \cdots \\ &\qquad \wedge v_n = w_{\alpha(n)} \wedge \varphi\big), \end{aligned}$$ avec les variables $w_1, \dots, w_m$, définit la partie annoncée, par la définition de la satisfaction et le lemme de coïncidence. Aucune substitution n'intervient, donc aucune capture.

Avec $\alpha$ l'identité, on peut ainsi écrire deux parties définissables de $\mathbb N^n$ avec les mêmes variables ; la conjonction, la disjonction et la négation donnent alors l'intersection, la réunion et le complémentaire. Si $B \subset \mathbb N^{n+1}$ est défini par $\psi$ et $v_1, \dots, v_{n+1}$, sa projection est définie par $\exists v_{n+1}\, \psi$ et $v_1, \dots, v_n$, par le lemme de coïncidence.

Les formules atomiques $v_3 = +\, v_1\, v_2$, $v_3 = \times\, v_1\, v_2$, $v_2 = S\, v_1$, $v_1 = 0$ et $v_1 = v_2$ définissent les parties annoncées.

(ii) L'ordre strict est définissable, puisque $x < y \iff \exists z\, (x + S(z) = y)$. Le graphe de $\beta$ aussi, puisque, par l'unicité du reste, la relation $v = \beta(a, b, i)$ équivaut à l'existence de $q$ et de $m$ tels que $m = S(S(i) \times b)$, $a = q \times m + v$ et $v < m$. Chacune de ces écritures se ramène à (i).

L'ensemble des fonctions partielles définissables contient les fonctions de base, définies par $y = 0$, $y = S(x)$ et $y = x_i$. Il est stable par composition, puisque $$\begin{aligned} &h(x) = y \iff \exists z_1 \cdots \exists z_m \\ &\quad \Big(\bigwedge_{l} g_l(x) = z_l \wedge f(z) = y\Big). \end{aligned}$$

Il est stable par minimisation, puisque $\mu y\, [f(x, y) = 0] = y$ équivaut à $$\begin{aligned} &f(x, y) = 0 \wedge \forall z\, \big(z < y \to {} \\ &\qquad \exists w\, (f(x, z) = w \wedge w \neq 0)\big). \end{aligned}$$

Il est stable par récurrence primitive. En effet, $h(x, y) = v$ équivaut à l'existence de $a$ et $b$ tels que $$\begin{aligned} &\beta(a, b, 0) = f(x), \\ &\forall i < y\ \ \beta(a, b, i + 1) = g\big(x, i, \beta(a, b, i)\big), \\ &\beta(a, b, y) = v, \end{aligned}$$ chaque égalité entre valeurs de fonctions s'écrivant avec des quantificateurs existentiels comme pour la composition. Sans paramètre, $f(x)$ est remplacé par l'entier initial $c$ de la récurrence, et la partie $\{c\}$ est définie par $v_1 = S \cdots S\, 0$, avec $c$ symboles $S$.

Si $h(x, y) = v$, les valeurs $h(x, 0), \dots, h(x, y)$ sont définies, et le lemme de la fonction β fournit $a$ et $b$ qui les codent. Réciproquement, si $a$ et $b$ conviennent, on montre par récurrence sur $i \leqslant y$ que $h(x, i)$ est défini et égal à $\beta(a, b, i)$.

(iii) Une relation récursive $R$ est l'ensemble $\{x : \chi_R(x) = 1\}$, définissable par (ii) et (i). Une partie récursivement énumérable est la projection d'une relation récursive. Pour $K$, on applique (i) avec $m = 1$ pour choisir la variable.