chx$$\def\lra{\leftrightarrow} \def\tx#1{\text{#1}} \def\line#1#2{\ & #1 \quad & \rm{(#2)}\\} \def\linet#1#2{\ & #1 \quad & \rm{#2}\\} \def\fa{\forall} \def\ex{\exists} \def\A{\mathcal{A}} \def\B{\mathcal{B}} \def\C{\mathcal{C}} \def\D{\mathcal{D}} \def\E{\mathcal{E}} \def\G{\mathcal{G}} \def\H{\mathcal{H}} \def\I{\mathcal{I}} \def\J{\mathcal{J}} \def\mK{\mathfrak{K}} \def\mN{\mathfrak{N}} \def\mM{\mathfrak{M}} \def\mA{\mathfrak{A}} \def\mB{\mathfrak{B}} \def\mC{\mathfrak{C}} \def\mD{\mathfrak{D}} \def\mL{\mathfrak{L}} \def\mR{\mathfrak{R}} \def\Ax{{\bf Ax}} \def\ax{\Lambda} \def\bl{\begin{aligned}} \def\el{\end{aligned}} \def\T{\mathscr{T}} \def\t{ {\bf t} } \def\f{ {\bf f} } \def\L#1{L(#1)} \def\eq{\equiv} \def\inp{\leftarrow} \def\la#1{\langle #1\rangle} \def\ov#1{\overline{#1}} \def\wff{{\bf Wff}} \def\so{{\scr O}} \def\vd{\vdash_{L(N)}} \def\ifff{\ {\rm iff}\ } \def\thm{\mathbf{Thm}} \def\mod{\mathrm{Mod}\ } \def\momg{{\mM_\omega}} \def\m{\mM} \def\st{{\mathrm{st}}}$$
对于 $\frak P$ 的非平凡子集 $\cal F$ , 集合 $\mathbb A:=\{x\in\N:\{x\}\in\cal F\}$ 不是递归的.
we prove the theorem through the unsolvability of halting problem
注意到 $\cal F$ 的补集也是非平凡的, 因此我们总是可以假定空函数 $\empty\in\cal F$ , 如果不然我们可以讨论 $\ov{\cal F}$ 的情形, 之后我们另取一部分递归函数 $g\notin\cal F$ .
函数 $U:=\lambda ix.\{i\}(x)$ 是部分递归函数.
显然 $U=\lambda ix.((\mu z)T^{(1)}(i,x,z))_0$ , 而 $T^{(1)}$ 是原始递归谓词, 根据 $\frak P$ 的定义可得 $U\in\frak P$ .
函数 $f:=\lambda xy.U(y,y)\cdot 0+g(x)$ 是部分递归函数.
之后我们关注构造出来的 $f$ 的性质, 对于任意的输入 $x,y\in\N$ , 如果 $y\in K$ 则 $f(x,y)=g(x)$ , 否则 $f(x,y)\uparrow$ . 由于 $f\in\frak P$ 故存在 $i_0\in\Phi$ 使得 $\{i_0\}=f$ , 于是由 I.8.52 对于任意的 $x,y\in\N$ 均有
$$U(x,y)=\{i_0\}(x,y)=\{\sigma(i_0,y)\}(x)$$于是对于 $y\in\N$ , 假定 $y\in K$ , 则对于任意输入 $x\in \N$ 均有 $\{\sigma(i_0,y)\}(x)=g(x)$ 从而 $\{\sigma(i_0,y)\}=g$ ; 而另一方面假定 $y\notin K$ , 则对于任意输入 $x\in\N$ 有 $\{\sigma(i_0,y)\}(x)\uparrow$ , 从而 $\{\sigma(i_0,y)\}=\empty$ .
接下来我们通过反证法来证明莱斯定理, 为导出矛盾, 假定 $\mathbb A$ 是递归集, 那么它的特征函数 $\chi_{\mathbb A}$ 是递归函数, 于是考虑构造递归函数
$$\varphi:=\lambda y.\chi_{\mathbb A}(\sigma(i_0,y))$$则对于任意 $n\in\N$ , 如果 $n\in K$ 则 $\{\sigma(i_0,n)\}=g\notin\cal F$ 从而 $\varphi(x)=1$ ; 另一方面如果 $n\notin K$ 则 $\{\sigma(i_0,n)\}=\empty\in\cal F$ 从而 $\varphi(x)=0$ , 故递归函数 $\varphi$ 是 $\ov K$ 的特征函数, 故 $K$ 也是递归集, 这与我们的结论矛盾了.