Caractérisations des ensembles récursivement énumérables

(a) ⇒ (b). Si $x \in A \iff \exists y\, R(x, y)$, la fonction $x \mapsto \mu y\, R(x, y)$ est récursive (Fonctions récursives, (iii)) et définie exactement sur $A$.

(b) ⇒ (a) et (c). Si $A = D(f)$, avec $f = \varphi_e$ (Kleene, (i)), alors $x \in A \iff \exists t\, T_1(e, x, t)$, avec $T_1$ primitive récursive. Si $A$ contient un élément $a$, la fonction $$g(w) = \begin{cases} (w)_0 & \text{si } T_1\big(e, (w)_0, (w)_1\big), \\ a & \text{sinon,} \end{cases}$$ est primitive récursive, et son image est $A$ : tout $x \in A$ est l'image de $w = 2^x 3^t$, pour un $t$ tel que $T_1(e, x, t)$.

(c) ⇒ (d). Une fonction primitive récursive est récursive (Fonctions récursives, (i)). L'ensemble vide est l'image de la fonction $x \mapsto \mu y\, [S(y) = 0]$, définie nulle part, qui est récursive.

(d) ⇒ (a). Soit $A$ l'image de $\varphi_e$. Une configuration terminale ne change plus ; ainsi, pour tout $t$ tel que $T_1(e, x, t)$, on a $\varphi_e(x) = U_1(e, x, t)$. Donc $$\begin{aligned} y \in A \iff{} &\exists w\ \Big(T_1\big(e, (w)_0, (w)_1\big) \\ &\wedge U_1\big(e, (w)_0, (w)_1\big) = y\Big), \end{aligned}$$ relation primitive récursive sous le quantificateur.

La dernière assertion est l'équivalence de (a) et (b), puisque les fonctions récursives d'une variable sont les $\varphi_e$.