ゲーデルの不完全性定理
ゲーデルの不完全性定理について調べようとしたら、Wikipediaの解説では、ちょっと専門的すぎて分からなかった。自然言語での解説を試みる他サイトでは、定義からのつながりがよく分からなかった。
で、あちこち調べた結果を、一応まとめてみる。
とりあえず落ち着くために調べたものであって、完全に理解できているわけではないと思う。
定義
Wikipediaには、こうある。
第1不完全性定理
自然数論を含む帰納的に記述できる公理系が、ω無矛盾であれば、証明も反証もできない命題が存在する。
第2不完全性定理
自然数論を含む帰納的に記述できる公理系が、無矛盾であれば、自身の無矛盾性を証明できない。
「命題」とは、「論理式」とも読み替えられて、「真(正しい)」と「偽(間違い)」にて判定される。プログラミング言語ぽく表現するなら、if文などの「判定式」で、「true」と「false」という結果が得られる。
ω無矛盾
これもWikipediaを引くとこうある(記号表現については、『数学記号の表 - Wikipedia』参照のこと)。
ω無矛盾 （オメガむむじゅん、omega consistency）とは、* 論理式Pがあり、P(0),P(1),P(2)・・・のすべてと、¬∀xP(x)が同時に証明されるような論理式Pが存在しないこと
を意味する。
通常の無矛盾性,* Pと¬Pとが同時に証明されるような論理式Pが存在しないこと
よりも強い条件を与える。
変数xを含む論理式Pにおいて、xがいろいろな値を取りうる。そのすべての取りうる値xについてPが真であるとき、同時にすべてのxについてPが偽である論理式Pが存在しないことを「ω無矛盾」という。
言ってることは分かるけど、それが何を示しているのか、分からない。まあ、あるがままなんだろうけど。
ω無矛盾であれば、無矛盾である。
第1不完全性定理
第1不完全性定理
自然数論を含む帰納的に記述できる公理系が、ω無矛盾であれば、証明も反証もできない命題が存在する。
「ゲーデル文」として知られる(らしい)、無矛盾な論理体系TにおけるGという命題を仮定する。Gの内容は「Gの証明は存在しない」。
Gが真であるならば、「Gの証明は存在しない」が真ということだが、その命題に従い、証明は存在しない。
Gが偽であるならば、「Gの証明は存在する」ことになるが、その証明可能なGの内容は「Gの証明は存在しない」であるため、矛盾する。
論理体系Tは無矛盾であるため、Gは真でなくてはならず、従ってその証明は存在しない。
つまりこのゲーデル文が、「証明も反証もできない命題」。
「ω無矛盾」とあえて指定してある理由は、分からない。
