ゲーデルの定理

質問

完全性定理では「任意のモデルで真である文はすべて１階述語論理で証明可能である」
不完全性定理では「自然数論を含む体系は無矛盾である限り、真であっても証明できない
命題が存在する」とありました。
それではこの２つの定理をペアノの公理系に当てはめると「全ての真である命題は証明可能」でありながらどこかに「真であっても証明できない命題が存在する」わけですか？

何だか矛盾するような感じがしますが、そんな訳ありませんよね。
どう考えたらよいのか教えてください。
よろしくお願いいたします。

回答No.1

rinkun · ベストアンサー

不完全性定理の記述が不正確なようです。正しくは「自然数論を含む体系は無矛盾である限り、証明も反証もできない命題が存在する」です。
# 元々は「ω無矛盾」が前提だが「無矛盾」でも成り立つらしい
# 参考: http://ja.wikipedia.org/wiki/%E3%82%B2%E3%83%BC%E3%83%87%E3%83%AB%E3%81%AE%E4%B8%8D%E5%AE%8C%E5%85%A8%E6%80%A7%E5%AE%9A%E7%90%86

モデルにおける真偽の概念と公理系における証明可能の概念を結ぶのが完全性定理です。
まず(1階述語論理の)公理系を一つ取ります。ある文がこの公理系で証明可能であれば、この公理系を満たす任意のモデルで真であることは明らかです。逆に「公理系を満たす“任意の”モデルで真になる文は、その公理系で証明可能である」ことを主張するのが完全性定理です。

一方で不完全性定理は公理系の完全性に関する問題で、この記述にはモデル(真偽の概念)は必要ありません。ただモデルにおいては全ての文は真か偽かの何れかですから、証明も反証もできない命題はそれ自身かその逆が真でかつ証明できない文になります。

さて、これらの定理をペアノの公理系に当てはめると、ペアノの公理系を満たすモデルを一つ取ると、そのモデルでは真だが証明できない命題があります(不完全性定理)。ただペアノの公理系を満たす任意のモデルで真になる命題は証明できます(完全性定理)。
矛盾はありませんね。

お礼

なるほど、そんなふうに考えれば良いのですね。
完全に分かったとは言えませんが、少し知識が増えました。
どうもありがとうございます。

補足

正直なところ、モデルというのが私にはよく分かりません。
ペアノの公理系といっても算数しか知りませんから。
ですから「任意のモデルで真」というのがキツイですね。
イメージがさっぱりわきません（これは質問ではないです）