第IV章 演習問題 [36]

普通に公理を再帰的関数によって数え上げる方法で \(\mathrm{ZF}\) を表現する式を \(\chi_0\) と書こう. このとき当然 \[ \begin{gather} \phi\in\mathrm{ZF}\;\rightarrow\;\mathrm{ZF}\,\vdash\,\chi_0(\ulcorner\phi\urcorner), \\ \phi\notin\mathrm{ZF}\;\rightarrow\;\mathrm{ZF}\,\vdash\,\neg\chi_0(\ulcorner\phi\urcorner) \end{gather} \]となっている. そして 式 \(\chi\) を \[ \chi(x)\equiv \chi_0(x)\land \mathrm{CON}\big(\{\,y\,:\,\chi_0(y)\land y\leq x\,\}\big) \]と定めよう. すると, \(\phi\notin\mathrm{ZF}\) のとき \(\mathrm{ZF}\vdash\neg\chi(\ulcorner\phi\urcorner)\) となることは明らかだし, \(\phi\in\mathrm{ZF}\) のときには, \(\phi\) 以下のゲーデル数をもつ有限個の公理の無矛盾性を \(\mathrm{ZF}\) が証明できることから \[ \mathrm{ZF}\;\vdash\;\mathrm{CON}\big(\{\,y\,:\,\chi_0(y)\land y\leq \ulcorner\phi\urcorner\,\}\big) \]であり, したがって \(\mathrm{ZF}\vdash\chi(\ulcorner \phi\urcorner)\) となる. つまり, \(\chi\) は \(\mathrm{ZF}\) を表現する.

\(\mathrm{ZF}\) において文の集合 \(\ulcorner\mathrm{ZF}\urcorner\) を \(\ulcorner\mathrm{ZF}\urcorner=\{\,x\,:\,\chi(x)\,\}\) と定めたとしよう. このとき, 反証可能な式 \(0\neq0\) の \(\ulcorner\mathrm{ZF}\urcorner\) からの証明図が与えられたとして, それに登場する公理のうちゲーデル数が最大のものを考えてそれが式 \(\chi\) をみたすことから矛盾を導く, という論法を \(\mathrm{ZF}\) において形式化すれば \(\mathrm{ZF}\,\vdash\,\mathrm{CON}(\ulcorner\mathrm{ZF}\urcorner)\) である.

ここで定義した式 \(\chi\) ともとの \(\chi_0\) との同値性は \(\mathrm{ZF}\) から証明できません. また, \(\chi_0\) は単に式の構文をチェックしているだけなので, \(\mathrm{ZF}^{-}-\mathrm{P}-\mathrm{Inf}\) のようなうんと弱い理論でも \(\chi_0\) が \(\mathrm{ZF}\) を表現することは確かめられますが, \(\chi\) が \(\mathrm{ZF}\) を表現する(各公理のゲーデル数が \(\chi\) をみたすことを証明する)ためには \(\mathrm{ZF}\) のフルパワーが要求されます. その意味でも, \(\chi\) は「これこれの形の式を \(\mathrm{ZF}\) の公理としよう」というわたくしたちの定義の素直な表現とはいえないのですが, それでも \(\mathrm{ZF}\) を表現していることは確かです. \(\mathrm{ZF}\) を表現する式が一意的に定まるわけではないというのがこの話の教訓といえるでしょう.

解答者: 藤田 博司 (公開日: 2011年6月30日)
2011年7月1日更新: 式の誤記を修正

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

演習問題一覧に戻る