不完全性定理を教えれ

ゲーデルの不完全性定理を分かりやすく教えてくれんか。

sine

んーと、何を教えて欲しいのかにも依るんですが。
第１不完全性定理自体の字面は、岩波数学辞典に依ると、
「自然数の理論を形式化して得られる形式的体系においては、
その体系が無矛盾である限り、必ず、Aおよびその否定が
ともに証明不可能な論理式Aが存在する」
ってことです。
ちょっと必要な要素を読み落としやすい言い方だなぁ、これ。

形式化とか形式的体系って言うのは、Hilbertの形式主義の考え
方でってことですね。だから、ここでいう公理って言うのは
有限の立場で与えられているっていうことになる。これ重要。
まあ平たく言えば、定義可能ってことですね。
そうじゃなくて、モデルとってきてそこで真な命題全部ぶち込んだ
公理系とか考えちゃうと、当然これは成り立たないわけです。

自然数の理論を、ってのも結構曖昧ですね。
要するに、普通の自然数論と相反しなければいいんですが。

そういう体系だと、「その体系の中で」それ自体もその否定も
証明できないような論理式があるってことですね。
「その体系の中で」ってのも重要で、より大きい体系の一部として
見てやれば全部の論理式を証明することも可能なわけで。(続く)

証明するってなると、これはかなり面倒です。
しかも内容がなく単に面倒な場所が多いので嫌われてます。
アイデアとしては、いわゆるGodel numberを使って、論理式とか
証明とかを全部、自然数論の中で帰納的にcodeして、あとは
対角線論法に持っていくってことなんですが。
帰納的にcode出来るかどうかが鍵だからそこで手は
抜けないのだけれども、でもほとんど単純作業になるんで。

にしても、第１不完全性定理を今の形で完全に証明したのは
GodelじゃなくてRosserなんですね。知らなかった。
Godelはω-無矛盾という無矛盾よりちょっと強い条件を使って
証明したようです(論文読んでいないので伝聞にて)。
もっとも、Godelのアイデアがこの定理の証明の中心で
あることには間違いないのですけれども。(続く)

第２不完全性定理は以下のようなもの。再び岩波数学辞典。
「自然数の理論を含む形式的体系Sが有限の立場で与えられ、
しかもSが無矛盾であるならば、Sのなかで形式化されるような
論法だけによっては、Sの無矛盾性を証明することは不可能である」

…なんでこっちでは有限の立場ときちんと断っているんだろう?
これは第１不完全性定理の系と言えると思います。
見落としやすい点はすでに第１の方で説明したので省略。
おまけにこっちの方がよりくどく書いてあるしね。

というわけで、Peano算術の中でからPeano算術の無矛盾性とか、
ZFCの中でZFCの無矛盾性とかを証明するのは不可能なわけです。
変なのは、逆に矛盾するような公理系ならば何でも証明できるから、
自分自身の無矛盾性も証明できちゃうってことですね。
まともな人は自分がまともだと説明できないのだけれども、
厨房はまともだと言い張れるってこと、かな?

とりあえずこんな感じで。
なんか疑問とか間違いとかあったらどうぞ。

っていうか、これ系の話やるの久しぶりだったので疲れた

げーでる　ですね。
俺も知りたいのでゼミでもやりますか？

岩波科学ライブラリーの「ゲーデルの謎を解く」って本が分かりやすいですよ。

うーん、自分の書き込みがあんまりにも不親切なんでやりなおしで
最初から書いてこうかと思ってたんだけど。
いい本があるならいいかな。ちょっと参考に見てみたいところだけど、
今海外なのでちょっと辛い。

＞７
そうなんですか？

age

前原昭二先生の数学基礎論の本がわかりやすくていいでしょう。
朝倉かどこかから出てたような気がしますが。

アンビリーバブル