第I章 演習問題 [24]

訳書59ページ下から7行めにある「定理14.2により \(\mathrm{ZF}\vdash\varphi\leftrightarrow\neg\chi(\ulcorner\psi\urcorner)\) となるような文 \(\psi\) があり」という部分の \(\varphi\) は \(\psi\) の間違い. (原書にない訳者のミスです. ごめんなさい.)

この問題は文中のヒントがほとんど解答そのものだが, 最後のところは少し解説がいるかもしれない. もしも \(T\) から証明される式の集合が再帰的なら, ヒントにあるようにその集合を表現する式 \(\chi\) が書ける. いっぽう, この式 \(\chi\) に対して, 定理14.2によって文 \(\psi\) を \[ \mathrm{ZF}\vdash\psi\leftrightarrow\neg\chi(\ulcorner\psi\urcorner)\tag{1} \] をみたすようにとれる.

もしも \(T\not\vdash\psi\) だったら \(\chi\) のとり方から \(\mathrm{ZF}\vdash\neg\chi(\ulcorner\psi\urcorner)\). これと \(\psi\) の条件(1)から \(\mathrm{ZF}\vdash\psi\). \(T\) は \(\mathrm{ZF}\) の拡大なので \(T\vdash\psi\). これは仮定に反するので, もともと \(T\vdash\psi\) だったわけだ. ところが今度は \(\chi\) のとり方から \(\mathrm{ZF}\vdash\chi(\ulcorner\psi\urcorner)\). これと \(\psi\) の条件(1)から \(\mathrm{ZF}\vdash\neg\psi\). \(T\) は \(\mathrm{ZF}\) の拡大なので \(T\vdash\neg\psi\). つまり \(T\) から \(\psi\) と \(\neg\psi\) の両方が証明できることになる. これは \(T\) が矛盾することを意味する.

ゲーデルの不完全性定理やタルスキの真偽の定義不可能性定理などは, このキューネン本ではやや不完全にしか扱われていないのですが, 前原昭二『数学基礎論入門』(朝倉書店), 田中一之編『ゲーデルと20世紀の論理学(ロジック)』第3巻(東京大学出版会), 新井敏康『数学基礎論』(岩波書店)などの本に詳しく書かれています.

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

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

演習問題一覧に戻る