§E19.29完全性と不完全性

0 と 1 からなる有限列$s$に対して、$T$を有限個の文で拡大した理論$T_s$を$s$の長さについての再帰で定める。$T_{()}=T$とし、$T_s$が定まったとき、$T_{s0}=T_s+R_{T_s}$、$T_{s1}=T_s+\neg R_{T_s}$とする。ここで$s0$、$s1$は$s$の末尾に$0$、$1$を加えた列であり、$R_{T_s}$は§E19.23 定義 4.1により$T_s$から定まる Rosser 文である。$T_s$が無矛盾ならば、$T_s$は$Q$を含み、有限個の文を加えた公理集合は計算可能に列挙することができるので、§E19.23 定理 4.2 (2)により$T_s\nvdash R_{T_s}$かつ$T_s\nvdash\neg R_{T_s}$である。よって$T_s$と$R_{T_s}$は定理 3.1の仮定をすべて満たし、$T_{s0}$と$T_{s1}$はともに無矛盾である。長さについての帰納法により、すべての$T_s$は無矛盾である。

無限列$b\in\{0,1\}^\omega$に対して$U_b=\bigcup_{n<\omega}T_{b|n}$とおく。$(T_{b|n})_{n<\omega}$は増大列であり各項が無矛盾であるから、§E19.11 補題 1.1により$U_b$は無矛盾である。§E19.11 定理 5.2により$U_b$を含む極大無矛盾な$L_A$理論$V_b$を一つ取る。この取り出しは各$b$について選択公理を用いる。§E19.11 補題 5.3 (2)により$V_b$は構文論的に完全であり、$T\subseteq V_b$である。

$b\neq b'$とし、$b|n=b'|n=s$かつ$b(n)=0$、$b'(n)=1$を満たす$n$を取る。$V_b$は$R_{T_s}$を含み、$V_{b'}$は$\neg R_{T_s}$を含む。$V_b$は無矛盾であるから$\neg R_{T_s}\notin V_b$であり、$V_b\neq V_{b'}$である。よって$b\mapsto V_b$は単射であり、$T$を含む構文論的に完全な無矛盾理論は少なくとも$2^{\aleph_0}$個存在する。一方、$L_A$文の集合は可算であるから、$L_A$理論の全体の濃度は$2^{\aleph_0}$以下である。したがって、ちょうど$2^{\aleph_0}$個存在する。

まず$R_T$が標準モデルで真であることを示す。$T\nvdash R_T$であるから、§E19.23 定義 1.2の標準モデルでの正確性により、どの標準自然数$p$についても$\operatorname{Prf}_T(\bar p,\ulcorner R_T\urcorner)$は標準モデルで偽である。したがって§E19.23 式 (R)の右辺の全称文は、含意の前件がすべての$p$で偽であるから標準モデルで真である。標準モデルは$Q$のモデルであるから、健全性により$R_T$は標準モデルで真である。

$\mathcal M\models T+\neg R_T$とし、$\mathcal M$が標準モデルと同型であると仮定する。§E19.8 系 2.4により$\mathcal M$と標準モデルは同じ文を満たすので、$\mathcal M\models R_T$となり、$\mathcal M\models\neg R_T$と両立しない。よって$\mathcal M$は標準モデルと同型でない。

$\mathcal N\models\neg\operatorname{Con}_T$であり、$\neg\operatorname{Con}_T$は$\neg\neg\exists p\,\operatorname{Prf}_T(p,\ulcorner0=S0\urcorner)$であるから、$\mathcal N\models\exists p\,\operatorname{Prf}_T(p,\ulcorner0=S0\urcorner)$であり、条件を満たす要素$a$が存在する。$a=\bar n^{\mathcal N}$を満たす標準自然数$n$があると仮定する。$T$は無矛盾であるから$\operatorname{Proof}_T(n,\ulcorner0=S0\urcorner)$は成り立たず、§E19.21 命題 5.2 (3)により$Q\vdash\neg\operatorname{Prf}_T(\bar n,\ulcorner0=S0\urcorner)$である。$Q\subseteq PA\subseteq T$であるから$\mathcal N\models Q$であり、健全性により$\mathcal N\models\neg\operatorname{Prf}_T(\bar n,\ulcorner0=S0\urcorner)$である。一方、$a=\bar n^{\mathcal N}$であるから$\mathcal N\models\operatorname{Prf}_T(\bar n,\ulcorner0=S0\urcorner)$となり矛盾する。よって$a$はどの$\bar n^{\mathcal N}$とも異なる。

標準モデルから$\mathcal N$への同型$h$があれば、$h$は$0$と$S$の解釈を保つので、各標準自然数$n$について$h(n)=\bar n^{\mathcal N}$である。$h$の全射性から$a=h(n)=\bar n^{\mathcal N}$を満たす$n$が存在し、前段に反する。よって$\mathcal N$は標準モデルと同型でない。メタ理論での$T$の無矛盾性と$\mathcal N\models\neg\operatorname{Con}_T$は、$\neg\operatorname{Con}_T$の証人が非標準要素であることによって両立する。