再帰的可算だが再帰的ではない集合から第1不完全性定理を導く
参考文献
Lem 5.4.8
$ A \sube \N^nについて，次の条件は同値である．
2. $ Aと$ \N^n \setminus Aのどちらもが再帰的可算集合 Thm 7.3.19
$ Tは$ \Sigma_1健全な理論とする．（ #TODO より詳細に条件を追記する） $ \varphi(x)は$ T上で$ Aを弱表現するとする． すなわち，任意の自然数$ a \in \Nについて$ a \in A \implies T \vdash \varphi(\overline{a})
このとき，$ T \nvdash \varphi(a)かつ$ T \nvdash \lnot\varphi(a)な$ aが存在する．
proof
1. $ A \coloneqq \{a \in \N \mid T \vdash \varphi(a)\}．
2. $ B \coloneqq \{b \in \N \mid T \vdash \lnot\varphi(b)\}とする．
3. $ b \in Bとすると$ T \vdash \lnot\varphi(b)．
4. $ \Sigma_1健全性より$ Tは無矛盾であり，$ T \nvdash \varphi(b)．
5. よって$ b \notin Aであり，$ B \sube \N \setminus A．
6. 今，$ B = \N \setminus Aと仮定すると破綻し，$ B \neq \N \setminus Aであることを示す
6_1. $ \N \setminus A \coloneqq \{a \in \N \mid T \vdash \lnot\varphi(a)\}である．
$ Bの定義より．
6_2. $ \mathcal{N} \vDash \mathrm{Pr}_T(\ulcorner \lnot\varphi(a) \urcorner) \iff T \vdash \lnot\varphi(a)
6_3. 以上より$ \N \setminus A \coloneqq \{a \in \N \mid \mathcal{N} \vDash \mathrm{Pr}_T(\ulcorner \lnot\varphi(a) \urcorner) \}
6_4. 6_3より$ \N \setminus Aは$ \Sigma_1集合であり，再帰的可算集合である． 6_5. 仮定より$ Aが，6_4より$ N \setminus Aが再帰的可算集合であるので，補題5.4.8より$ Aは再帰的集合である 7. 5,6より，$ B \sub \N \setminus Aである．
8. 7より，$ a \in \N \setminus Aかつ$ a \notin Bとなる$ aが存在する．
この$ aについて，
$ T \nvdash \varphi(a) \impliedby a \notin A \impliedby a \in \N \setminus A
$ T \nvdash \lnot\varphi(a) \impliedby a \notin B
十分に強力な理論$ Tには証明も反証も出来ない文$ \sigmaが存在する．すなわち$ T \nvdash \sigmaかつ$ T \nvdash \lnot\sigma．