\(X\) を再帰的でない r.e. 集合とすると，\(X \subseteq \mathbb{N}\) なので Exercise 3.2(a) より \(T_0\) において \(X\) を numerate し，\(T_1\) において \(\mathbb{N}\) を numerate する論理式 \(\xi(x)\) がとれる． 各再帰的関数 \(f\) について， \[ Y_f = \{n : T_0 \vdash \xi(n)\ \&\ T_1\ における\ \xi(n)\ の証明\ p\ があって\ T_0\ において\ \leq f(p)\ 以下に\ \xi(n)\ の証明がない\} \] \[ P_f = \{n : T_1\ における\ \xi(n)\ の証明\ p\ があって\ T_0\ において\ \leq f(p)\ 以下に\ \xi(n)\ の証明がない\} \] と定める． 全ての \(n\) について \(T_1 \vdash \xi(n)\) となるため，\(P_f\) は再帰的集合である． また \(T_0 \vdash \xi(n) \iff n \in X\) なので \(Y_f = X \cap P_f\) である． 他方 \(n \notin X\) ならば \(T_0 \nvdash \xi(n)\) なので \(n \in P_f\) となる． したがって \[ n \in X \iff n \in Y_f\ または\ n \notin P_f \] となる． いま \(Y_f\) が再帰的となるような再帰的関数 \(f\) があるとすると \(X\) も再帰的となるためにおかしい． したがって \(Y_f\) が再帰的となるような再帰的関数 \(f\) は存在しない．