野矢論理学 5章

ゲーデルの不完全性定理の概観。なぞっても面白くないので自分なりに再構成。

自然数論を含む公理系Nは、矛盾しているか、不完全である（ゲーデルの第一の不完全性定理）。そして、Nの無矛盾性は、有限の立場では証明することができない（ゲーデルの第二の不完全性定理）。

そもそも、理論の無矛盾性などのメタな問題の議論は、理論内部で行うような式変形ではなく、他の何らかの手段で検証されるべき性質のものである。とはいえ、我々はヒルベルト的な考え方、すなわち有限の立場で（すなわち数学的帰納法などを使った構成的立場で）メタな議論を行うことを常としている。命題論理や述語論理の完全性や無矛盾性はその方法で示される。一方、自然数論は、その方法では完全性や無矛盾性を示せないとゲーデルが指摘した。なおゲンツェンは、別の立場（超限帰納法）で議論すれば、無矛盾性が示せると指摘した。我々は、理論に対するメタな議論をする際にどのような方法に訴えるべきかについて、再考するべきかもしれない。

第一不完全性定理は、実際に「私は証明できない」という意味の命題が存在することで示される。「・は証明できる」という述語はメタな述語であり、1階述語論理における述語ではないが、ヒルベルト流メタ議論は、自然数論と同一の道具立てを使っているため、「・は証明できる」という述語を自然数論Nにおける述語にすることができる。そして、対角化定理を利用することで、「私が証明できない」という意味の命題の存在を示すことができる。第二不完全性定理は、第一不完全性定理をちょろっと使うとすぐに出てくる。

一応ゲーデルの不完全性定理に関してその定理の意味とそれを取り巻く議論は俯瞰できるようになった。定理の証明はざっと読んだ感じなのでもう少し時間をかけてゆっくり見ていきたい。

野矢先生の本は、対話形式ということもあり、素朴に思うような疑問にきちんと答えてくれるのがありがたい。この本によって不完全性定理の意味を、過大評価せずに見つめなおすことができ、また理論に関するメタ的な理解が深まったように思う。

以上で野矢論理学読了。