数学基礎論講義をこっそり読む（その６） - Finite Groups Fun 有限群あるいはちょこっと計算ファンの日記

またもや重箱の隅をつついて遊ぶ探究ではありますが、p.54　補題4.15で『 AがREならば [tex:\forall y

$K_1$ が再帰的でないことの証明(ほとんどRiceの定理の証明)：

再帰的であると仮定して、その特性関数を $f$ とする。
また $\varphi(e)=\{e\}(e)-\{e\}(e)+1$ と定義すると $\varphi(e)$ は $K$ (定理4.19)をREとして特徴づける再帰的部分関数となる。 $dom(h)\ne\phi$ なるような再帰的部分関数 $h(x)$ を一つ選んで、 $F(x,y)\equiv \varphi(x)\cdot h(y)$ と定義する。定理4.8（パラメタ定理）から原始再帰的関数 $g(x)$ があって、 $\{g(x)\}(y)=F(x,y)$ が成立する。
さて、再帰的関数 $f(g(x))$ を考えると $g$ の作り方から

$x\in K \Rightarrow \{g(x)\}(y)=F(x,y)=h(y) \Rightarrow g(x)\in K_1 \Rightarrow f(g(x))=1$
$x\notin K \Rightarrow \{g(x)\}(y)=F(x,y)=\mbox{undefined} \Rightarrow g(x)\notin K_1 \Rightarrow f(g(x))=0$
となり、 $f(g(x))$ が $K$ の再帰的集合としての定義を与えることになり、矛盾である。□

上の証明中で、 $\varphi(e)$ がスイッチのように再帰的部分関数を切り替える働きをしており、再帰的部分関数をそのコードで代表させたとき、その再帰的部分集合がどんなものであっても、同様の論法により、それらは自明なもの（空集合か全部）しかないというRiceの定理が導かれます。

さて、最後に問題7です。見かけはややこしいですが、証明は簡単です。ヒントにある、 $d$ について、 $\{d\}(d)$ を計算してみますと、

$\{d\}(d)=0 \Rightarrow d\in A \Rightarrow d\in C \Rightarrow \{d\}(d)=1$

$\{d\}(d)=1 \Rightarrow d\in B \Rightarrow d\notin C \Rightarrow \{d\}(d)=0$
(最後は $\{d\}(x)$ が $C$ の特性関数であることを用いた。）となり、いずれも矛盾します。この問題7は、宿題であった本テキストのPart Aの冒頭の二番目の問題の解答を与えています。