第IV章 演習問題 [31]

可算個の変数記号をもち関係記号として等号 \(=\) と要素所属関係 \(\in\) だけをもつ集合論の言語 \(\mathcal{L}_{\in}\) が適切にゲーデル数化されているとすれば, \(\mathrm{ZF}\) の公理をゲーデル数の小さい順に並べた列 \(\langle\, \varphi_i\,:\,i<\omega\,\rangle\) は再帰的関数である. そこでこの関数は \(\mathrm{ZF}\) において式で表現され, すべての“本当の”自然数 \(n\) に対して \[ \begin{gather} n\text{ がZFの公理のゲーデル数}\;\rightarrow\;\mathrm{ZF}\vdash \exists i(\ulcorner n\urcorner=\varphi_i)\\ n\text{ がZFの公理のゲーデル数でない}\;\rightarrow\;\mathrm{ZF}\vdash \forall i(\ulcorner n\urcorner\neq\varphi_i) \end{gather} \] となっている.

第I章第14節で論じられたように一階述語論理の証明概念を形式化することを通じて, 三つの自由変数 \(u,v,w\) についての式 \(\chi_{\mathrm{pf}}^u(v,w)\) を, 《\(\,u\) は文の集合であり, \(v\) は式の列, \(w\) は式であって, 列 \(v\) は \(u\) からの \(w\) の形式的証明になっている》という述語を表現するように定義できる. これによって, ただひとつの自由変数 \(u\) に関する \[ \mathrm{CON}(u)\;\leftrightarrow\;\neg\exists v\chi^u_{\mathrm{pf}}(v,\ulcorner 0\neq0\urcorner) \] という式を定義しよう(→訳書p.53, 原著p.41). このとき, \(\mathrm{CON}(u)\) は 《\(\,u\) は無矛盾である》 という述語に対応する. ただし, 内容的な無矛盾性を(第I章定理14.1の意味で)表現するわけではない.

さきに定義した公理の列 \(\langle\,\varphi_i\,;\,i<\omega\,\rangle\) と \(\mathrm{CON}(u)\) から, 文の集合 \[ B=\big\{\, \varphi_x\,:\,x\in\omega\land \mathrm{CON}\big(\{\,\varphi_i\,:\,i\leq x\,\}\big) \,\big\} \]が \(\mathrm{ZF}\) において定義できる. この \(B\) は, 形式化された理論でシミュレートするメタ理論で無矛盾性を保証できる \(\mathrm{ZF}\) の最大の切片であり, 《\(\,B\) が無限集合であること》と \(\mathrm{CON}(\ulcorner{\mathrm{ZF}}\urcorner)\) と \(B=\ulcorner \mathrm{ZF}\urcorner\) は \(\mathrm{ZF}\) のもとで同値である. \(\mathrm{ZF}\) が実際に矛盾するのでない限り, \(\mathrm{CON}(\ulcorner{\mathrm{ZF}}\urcorner)\) は \(\mathrm{ZF}\) にとって決定不可能な命題であるから, \(B\) が有限集合か無限集合か, 有限だとしたらいくつの要素からなるか, そういったことを \(\mathrm{ZF}\) では決定できない. しかしなにはともあれ, 定義上 \[ \mathrm{ZF}\vdash\mathrm{CON}(B) \]ではある.

言語 \(\mathcal{L}_{\in}\) と文の集合 \(B\) が明示的に定義された可算集合であり, また \(\mathrm{CON}(B)\) が \(\mathrm{ZF}\) の定理であることによって, ゲーデルの完全性定理の証明がいたって実効的に \(\mathrm{ZF}\) において遂行できる. つまり, まずは \(\mathcal{L}_{\in}\), \(B\) のヘンキン化 \(\mathcal{L}_{\in}^*\), \(B^*\) を実効的に定義でき, \(\mathcal{L}_{\in}^*\) の文を数えあげる列 \(\langle\,\theta_i\,:\,i<\omega\,\rangle\) を明示的に定義できるので, \[ C_0 = B^*, ~~ C_{i+1} = \begin{cases} C_i, &\text{if }\exists v\,\chi_{\mathrm{pf}}^{C_i}(v,\neg \theta_i),\\ C_i\cup\{\theta_i\}, &\text{otherwise} \end{cases} \]によって順次 \(C_i\) を定め \(C=\bigcup_{i<\omega}C_i\) とすれば \(B^*\) の極大無矛盾拡大 \(C\) が明示的に定義される. 選択公理を使う必要もないし, できあがった \(\mathcal{L}_{\in}^*,C\) は明示的に式によって定義できる. そこで, \(\mathcal{L}_{\in}^*\) のスコーレム定数全体の集合を \[ c\sim d\;\leftrightarrow\;\ulcorner c=d\urcorner\in C \] という同値関係で割った商集合 \(M\) と, \[ c\mathbin{E}d\;\leftrightarrow\;\ulcorner c\in d\urcorner\in C \] という(同値関係と整合的な)二項関係 \(E\) を定義して, \[ \mathrm{ZF}\vdash\forall s\,\big(\,s\in B\,\rightarrow\,(M,E)\models s\,\big) \]となることが確認できる.

ここまでは, 考えている理論が \(\mathrm{ZF}\) である理由はなにもなく, \(\mathrm{ZF}^{-}-\mathrm{P}\) の再帰的な拡大であれば何でもよかった. しかしながら, \(\mathrm{ZF}\) の各々の公理 \(\phi\) について \[ \mathrm{ZF}\vdash \ulcorner\phi\urcorner\in B \]となることを示すにあたって, \(\mathrm{ZF}\) の真価が発揮される. この \(\phi\) はなにか“本当の”自然数 \(m\) について \(\varphi_m\) と一致するはずであり, \(\mathrm{ZF}\) が自分自身の任意の有限部分の無矛盾性を証明できることから \[ \mathrm{ZF}\vdash\mathrm{CON}(\{\,\varphi_i\,:\,i\leq \ulcorner m\urcorner\,\}) \]となり \(\mathrm{ZF}\vdash\ulcorner\phi\urcorner\in B\) を得る. \(\mathrm{ZF}\) が自分自身の有限部分の無矛盾性を証明できるというのは, 反映原理からの帰結であって, これには冪集合の公理と基礎の公理を必要とする.

こうして, \(\mathrm{ZF}\) の“本当の”公理 \(\phi\) のそれぞれについて, 個別には \[ \mathrm{ZF}\vdash \big(\,(M,E)\models \ulcorner\phi\urcorner\,\big) \]となることがわかる. あとは, メタ理論における式の構成にかんする帰納法によって, \[ \mathrm{ZF}\vdash\forall t\in M^{<\omega}\Big(\big(\,(M,E)\models\ulcorner\theta\urcorner[t]\,\big)\,\rightarrow\,(\theta(t))^{M,E}\,\Big) \](ただし \(\theta(t)\) は式 \(\theta\) の自由変数 \(\mathrm{v}_i\) へ \(t(i)\) を代入したもの, という意味) となることを検証すれば, \(\mathrm{ZF}\) の“本当の”公理 \(\phi\) のそれぞれについて, \[ \mathrm{ZF}\vdash \phi^{M,E} \]となることが確かめられる.

完全性定理については, 廣瀬健・横田一正『ゲーデルの世界』(海鳴社, 1985年), 『ゲーデルと20世紀の論理学』第2巻(東京大学出版会, 2006年), 新井敏康『数学基礎論』(岩波書店, 2011年) などを見てください. 拙ノート『弱コンパクト基数』(2009年, PDFファイル)のサブセクション5.Cでも証明を述べています.

解答者: 藤田 博司 (公開日: 2011年6月28日)

この解答に不具合を発見した方はぜひご指摘ください.

演習問題一覧に戻る