関数と集合の再帰性についてのメモ

参考文献

菊池誠; "不完全性定理"

各々の関数が原始再帰的関数であることはn番目の素数を返す関数は原始再帰関数であるを参照．

y.; "再帰的関数"

Prop 1.

関数が計算可能である$ \iff再帰的関数である．

remark

計算可能な関数が何を指しているのかは，ここではTuringマシンで計算可能ということとする．

Church-Turingのテーゼ

計算可能とは，Turingマシンで計算可能ということとする．

再帰的関数はTuringマシンで計算可能を参照．

Lem 1

1. $ A \sube \N^n．$ Aが原始再帰的集合/再帰的集合なら，$ \N^n \setminus Aも原始再帰的集合/再帰的集合

proof:

1. $ Aの特性関数$ \chi_Aとすると$ \chi_{\N^n \setminus A}(\vec{x}) \coloneqq 1 \ominus \chi_{A}(\vec{x})

2. 補正付き減算$ \ominusは原始再帰的関数

2. $ A,B \sube \N^n．$ A,Bが原始再帰的集合/再帰的集合なら，$ A \cup B, A \cap Bも原始再帰的集合/再帰的集合

proof:

1. $ \chi_{A \cup B} \coloneqq \min (\chi_A(\vec{x}), \chi_B(\vec{x}))

2. $ \chi_{A \cap B} \coloneqq \max (\chi_A(\vec{x}), \chi_B(\vec{x}))

3. $ \min,\maxは原始再帰的関数

3. $ A \sube \N^{n+1}とする．$ Aが原始再帰的集合/再帰的集合なら，次の$ B,Cも原始再帰的集合/再帰的集合

$ B \coloneqq \{ (\vec{x},y) \in \N^{n+1} \mid \exists_{z<y}\lbrack (\vec{x},z) \in A \rbrack \}

$ C \coloneqq \{ (\vec{x},y) \in \N^{n+1} \mid \forall_{z<y}\lbrack (\vec{x},z) \in A \rbrack \}

proof:

1. $ \chi_B(\vec{x},y) \coloneqq \mathrm{plus?}\left( \Sigma_{z<y}\lbrack\chi_A(\vec{x},z) \rbrack\right)

2. $ \chi_B(\vec{x},y) \coloneqq \mathrm{plus?}\left( \Pi_{z<y}\lbrack\chi_A(\vec{x},z) \rbrack\right)

3. 正数判定$ \rm{plus?}，有界和$ \Sigma，有界積$ \Piは原始再帰的関数

Lem 2

$ Aが再帰的集合$ \iff$ A = \{ \vec{x} \in \N^n \mid f(\vec{x}) = 0 \}となる全域再帰関数$ fが存在する．

proof:

$ \impliesの証明: $ f(\vec{x}) \coloneqq 1 \ominus \chi_A(\vec{x})とすれば要件を満たす．

$ \impliedbyの証明:

$ fを全域再帰関数とし，$ A \coloneqq \{ \vec{x} \in \N \mid f(\vec{x}) = 0\}とする．

$ \chi_A(\vec{x}) \coloneqq 1 \ominus \mathrm{plus?}(f(\vec{x}))であり，Lem1の注意より$ \chi_Aは再帰関数になる

Def: $ \Nの可算 / 再帰的可算集合

$ A \sube \Nが可算$ \iff$ A = \mathrm{range}(f)となる部分関数$ f:\N\to\Nが存在する

このとき$ A = \{ f(0),f(1),f(2),\dots \}でひたすら列挙し続ける

$ A \sube \Nが再帰的可算集合(r.e.)$ \iff$ A = \mathrm{range}(f)となる部分再帰関数$ f:\N\to\Nが存在する

remark: $ A \neq \emptysetのとき，$ fは全域関数となる．Lem3．

remark:一般の$ \N^nに対しては後で拡張される．

Lem 3

$ A \sube \Nで$ A \neq \emptysetのとき，

$ Aが再帰的可算集合$ \iff$ A = \mathrm{range}(f)となる全域再帰関数$ f:\N\to\Nが存在する

proof:

$ \impliedbyは定義より自明．

$ \implies #TODO

Lem 4

$ A \sube \N

$ Aが再帰的可算集合$ \iff$ A = \{ x \in \N \mid g(x) = 0 \}となる再帰的関数$ g:\N\to\Nが存在する

proof:

#TODO

Def: $ \N^nの再帰的可算集合

$ A \sube \N^nが再帰的可算集合$ \iff$ A = \{ \vec{x} \in \N^n \mid g(\vec{x}) = 0 \}となる再帰的関数$ g:\N^n\to\Nが存在する

remark:

Lem4の$ \impliedbyを$ 1 \leq nに一般化したものと考えよ

Cor 1

再帰的集合は再帰的可算集合である．

proof:Lem2より．

remark:

逆は常には成り立たない．Cor2.

remark

$ A \sube \N^nについて．

定義より，$ Aが再帰的可算集合なら，$ A = \{ \vec{x} \in \N^n \mid f(\vec{x}) = 0 \}となる再帰関数$ fが存在する．

Lem2より，$ Aが再帰的集合なら，$ A = \{ \vec{x} \in \N^n \mid f(\vec{x}) = 0 \}となる全域再帰関数$ fが存在する．

ここから，集合の可算性は関数の全域性と対応していると言える．

Cor 2

Cor 1の逆は常には成り立たない．すなわち

再帰的可算だが再帰的ではない集合が存在する．

proof 1:

Gödelの不動点補題を使う．

proof 2:

再帰定理を使う．

篠田寿一『帰納的関数と述語』参照．

remark

例としては，Kolmogorov複雑度的な乱数の集合がある．

remark

そのような集合から第1不完全性定理を導ける．

再帰的可算だが再帰的ではない集合から第1不完全性定理を導くを参照．

Lem 5

Lem1の2及び3は再帰的可算集合でも成り立つ．すなわち

$ A,B \sube \N^nが再帰的可算集合なら，$ A \cup B, A \cap Bも再帰的可算集合．

$ A \sube \N^{n+1}とする．$ Aが再帰的可算集合なら，次の$ B,Cも再帰的可算集合．

$ B \coloneqq \{ (\vec{x},y) \in \N^{n+1} \mid \exists_{z<y}\lbrack (\vec{x},z) \in A \rbrack \}

$ C \coloneqq \{ (\vec{x},y) \in \N^{n+1} \mid \forall_{z<y}\lbrack (\vec{x},z) \in A \rbrack \}

proof: Lem1の証明をそのまま実行する．

Lem 6

$ A \sube \N^nについて

$ Aが再帰的集合$ \iff$ A, \N \setminus Aの両方が再帰的可算集合

proof:

$ \implies

1. $ Aが再帰的可算集合なのはCor1より明らか．

2. Lem1より$ \N \setminus Aは再帰的集合

3. Cor1より$ \N \setminus Aは再帰的可算集合．

$ \impliedby

1 .$ A, \N \setminus Aの両方が再帰的可算集合とする．

2. 定義より次の部分再帰関数$ f,gが存在する．

$ A = \{ \vec{x} \in \N^n \mid f(\vec{x}) = 0 \}となる$ f:\N\to\N

$ \N \setminus A = \{ \vec{x} \in \N^n \mid g(\vec{x}) = 0 \}となる$ g:\N\to\N

3. $ h:\N\to\Nを以下のように約束すると，$ hは全域再帰関数となる．

$ f,gを並列に計算し，

$ f(\vec{x}) = 0のとき$ h(\vec{x}) = 0

$ g(\vec{x}) = 0のとき$ h(\vec{x}) = 1

$ A \cup (\N^n \setminus A) = \N^nかつ$ A \cap (\N^n \setminus A) = \emptysetであることに注意すると定義より次のことが成り立つ．

$ f(\vec{x})が停止しない，または$ f(\vec{x}) \neq 0のとき，

$ \vec{x} \notin Aであり$ \vec{x} \in \N \setminus Aなので，

必ず$ g(\vec{x}) = 0

$ f(\vec{x}) = 0のとき，

$ \vec{x} \in Aであり$ \vec{x} \notin \N \setminus Aなので，

必ず$ g(\vec{x}) \neq 0

逆もまた然り．

すなわち，$ f,gは任意の$ \vec{x} \in \N^nに対し，どちらか一方だけが$ 0を出力する．

よって$ hは全域性がある．

$ hが再帰関数なのは$ f,gより自明．

4. $ A = \{ \vec{x} \in \N^n \mid h(\vec{x}) = 0 \}とすればLem2より$ Aは再帰的集合となる．

Lem 7

Lem1の1の再帰的可算集合版は成り立たない．すなわち，

再帰的可算集合の補集合が再帰的可算集合であるとは限らない．

proof:

1. 「再帰的可算集合の補集合は再帰的可算集合である」と仮定する．

2. $ Aが再帰的可算集合だとする．

3. 仮定より，$ \N \setminus Aも再帰的可算集合となる．

4. 2,3とLem6より，$ Aは再帰的集合となる．

5. 整理すると，$ Aが再帰的可算集合$ \implies$ Aが再帰的集合である

6. ところが実際には再帰的可算だが再帰的ではない集合が存在するため，破綻している．

Lem 8

Lem 5の$ \existsの非有界版が再帰的可算集合版では成り立つ．すなわち

$ A \sube \N^{n+1}が再帰的可算集合なら，$ B' \coloneqq \{ (\vec{x},y) \in \N^{n+1} \mid \exists_{y}\lbrack (\vec{x},y) \in A \rbrack \}は再帰的可算集合．

$ \existsから有界の制限$ z<yの制限が取り払われたことに注意．

proof:

1. 定義より$ A = \{ (\vec{x},y) \in \N^{n+1} \mid f(\vec{x},y) = 0 \}となる再帰的関数$ f:\N^{n+1}\to\Nが存在する

2. $ g:\N^n\to\Nを次のように約束する．

$ \vec{x} \in \Nとし，$ f(\vec{x},0),f(\vec{x},1),f(\vec{x},2),\dotsと計算していく．

何らかの$ yで$ f(\vec{x},y) = 0となったとき，$ g(\vec{x}) = 0とする．

そうでないとき，$ g(\vec{x})は未定義動作．

3. $ gは明らかに計算可能なので，Prop1より再帰的である．

4. $ B'の定義より$ B' \coloneqq \{ x \in \N^n \mid g(\vec{x}) = 0\}とすればよい．

5. 3,4より$ B'は再帰的可算集合．

remark

$ A \sube \N^{n+1}が再帰的可算集合であっても，$ C' \coloneqq \{ (\vec{x},y) \in \N^{n+1} \mid \forall_{y}\lbrack (\vec{x},y) \in A \rbrack \}が再帰的可算集合であるとは限らない．

証明で約束した$ gは

$ \exists_{y}\lbrack (\vec{x},y) \in A \rbrackが正しいとき，その事実を有限の時間で確かめることが出来ることを確認している．

大雑把には，正しいときそこで計算を打ち切ることが出来るので，$ gの計算はそのうち終わる．

他方，$ \forall_{y}\lbrack (\vec{x},y) \in A \rbrackは正しくとも，その事実は有限の時間で確かめることはできない．

$ (\vec{x},0),(\vec{x},1),(\vec{x},2) \in Aだったとしても$ (\vec{x},3) \in Aが正しい保証はどこにもない．

延々に繰り返す必要がある．計算を打ち切ることが出来ない．

Lem 9

$ f:\N^n\to\Nとし，関数のグラフ$ G_f \coloneqq \{ (\vec{x},f(\vec{x})) \mid \vec{x} \in \N^n \}とする．

$ fが再帰的関数$ \iff$ G_fが再帰的可算集合

proof:

$ \implies

1. $ fが再帰関数とする．

2. $ g(\vec{x},y) \coloneqq 1 \ominus \mathrm{eq?}(f(\vec{x}),y)とする．

$ \mathrm{eq}?(x,y) = \begin{cases} 1 & (x = y) \\ 0 & (x \neq y) \end{cases}とする．原始再帰的関数である．

すなわち$ gは$ \mathrm{neq}?(f(x),y) = \begin{cases} 1 & (f(\vec{x}) \neq y) \\ 0 & (f(\vec{x}) = y) \end{cases}に相当する．

3. $ G_f \coloneqq \{ (\vec{x},y) \mid g(\vec{x},y) = 0 \} とすれば要件を満たす．したがって$ G_fは再帰的可算集合．

$ \impliedby

1. $ G_fが再帰的可算集合であるとする．

2. 定義より$ G_f = \{ (\vec{x},y) \in \N^n \mid g(\vec{x},y) = 0 \}となる再帰的関数$ g:\N^{n+1}\to\Nが存在する

3. $ f:\N^n\to\Nを次のように約束する．

$ g(\vec{x},0),g(\vec{x},1),g(\vec{x},2),\dotsを計算する．

最初に$ g(\vec{x},y) = 0となったとき，$ f(\vec{x}) = yとして計算を終了する．

4. $ fは明らかに計算可能なので，Prop1より再帰的関数．

Lem 10

Lem9の$ fが全域的な関数である場合は$ G_fは再帰的集合となる．すなわち．

$ f:\N^n\to\Nは全域的とし，関数のグラフ$ G_f \coloneqq \{ (\vec{x},f(\vec{x})) \mid \vec{x} \in \N^n \}とする．

$ fが再帰的関数$ \iff$ G_fが再帰的集合

proof:

$ \implies

1. Lem9の$ \impliesにおいて$ gも全域的になる．

2. Lem2より，$ G_fは再帰的集合

$ \impliedby

1. Cor1より$ G_fが再帰的集合$ \implies$ G_fが再帰的可算集合

2. Lem9より明らか．