Théorème de Rice

Notons $I_{\mathcal C}$ cet ensemble et $\varnothing$ la fonction définie nulle part. Comme $I_{\mathcal C}$ et $\mathbb N \setminus I_{\mathcal C} = I_{\mathcal C'}$, où $\mathcal C'$ est le complémentaire de $\mathcal C$, sont récursifs en même temps, et que $\mathcal C'$ vérifie les mêmes hypothèses, on peut supposer que $\varnothing \notin \mathcal C$. Soit $\psi \in \mathcal C$.

La fonction de deux variables $$\theta(e, x) \simeq P^2_1\big(\psi(x), \varphi_e(e)\big)$$ est récursive, par la fonction universelle (Kleene, (ii)) et la composition ; elle vaut $\psi(x)$ si $e \in K$, et n'est définie nulle part en $x$ si $e \notin K$. Soit $b$ un indice de $\theta$ ; par le théorème s-m-n, il existe une fonction primitive récursive $e \mapsto s(b, e)$ telle que $\varphi_{s(b, e)}(x) \simeq \theta(e, x)$.

Ainsi $\varphi_{s(b, e)} = \psi \in \mathcal C$ si $e \in K$, et $\varphi_{s(b, e)} = \varnothing \notin \mathcal C$ sinon : $$e \in K \iff s(b, e) \in I_{\mathcal C}.$$ Si $I_{\mathcal C}$ était récursif, $K$, son image réciproque par une fonction primitive récursive, le serait aussi (Récursif, r.e., (iii)), contrairement à l'indécidabilité de l'arrêt.