Deux ensembles récursivement énumérables récursivement inséparables

Par la forme normale de Kleene, $\varphi_e(e) \simeq U_1\big(e, e, \mu t\, T_1(e, e, t)\big)$. Ainsi, pour $i \in \{0, 1\}$, $$\begin{aligned} e \in A_i \iff \exists t\ \big(&T_1(e, e, t) \\ &\wedge \forall t' < t\ \neg T_1(e, e, t') \\ &\wedge U_1(e, e, t) = i\big), \end{aligned}$$ et la relation entre parenthèses est primitive récursive, par la quantification bornée (Clôture, (iii)), donc récursive (Fonctions récursives, (i)) : $A_0$ et $A_1$ sont récursivement énumérables. Ils sont disjoints, puisque $\varphi_e(e)$ a au plus une valeur.

Soit $C$ un ensemble récursif tel que $A_0 \subset C$ et $C \cap A_1 = \varnothing$. Sa fonction caractéristique $\chi_C$ est récursive et totale ; par le point (i) de la forme normale de Kleene, elle a des indices, et l'on note $d$ le plus petit : $\varphi_d = \chi_C$. Si $d \in C$, alors $\varphi_d(d) = 1$, donc $d \in A_1$, ce qui contredit $C \cap A_1 = \varnothing$. Si $d \notin C$, alors $\varphi_d(d) = 0$, donc $d \in A_0 \subset C$, ce qui est absurde. Un tel $C$ n'existe donc pas.