■
ゲーデルの不完全性定理をお教えください。
https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1410933224
これは、「そもそも何でこんなことが出てきたのか?」というところから始めないとよくわかりません。
数学の証明問題では、ずっと証明していくとどこかで、当たり前すぎて証明できないようなところに当たってしまうことがあります。
パスカルは「誰もが当たり前だと思う”真”であること」を公理としました。
「証明問題は、この公理から始めるべきで、公理自身は証明できない」としました。ところが、数学が発展してくると、負の数や虚数などが出てきました。こうなると「誰もが当たり前だと思う”真”であること」というのが非常に怪しくなってきました。
そこで、20世紀初頭にヒルベルトなどの学者が、「公理というのは単なる基本ルールである。それが現実的かどうかは関係ない。」
としました。いくつかの公理をまとめたセットを公理系といいます。とにかく公理系を認めてしまい、それを採用すれば何が言えるかということを考えるのが現代の数学なわけです。さて、公理は現実的である必要はないのですが、少なくとも二つのことが要求されます。
それが完全性と無矛盾性です。
無矛盾性というのは、その公理系で何か問題を考えるときに、矛盾する結果を引き起こさないこと。
完全性は、与えられた公理のセットだけを使って、どんな命題にも真か偽を決定できるということです。
当然の要求ですが、これが結構難しいのです。これは、少年マンガを考えるとわかりやすいです。
多くの少年マンガはストーリーが現実離れしています。しかし、だからダメということはありません。
これは、「公理系は現実離れしていてもかまわない」というのと同じです。
そのマンガの中だけで通用する設定というのがあり、それに沿っていれば現実的かどうかは関係ありません。ところが、基本設定が少なすぎる状況で、連載が長期に渡ると、時として、主人公がすでに示された設定の中だけでピンチから脱出できないなんてことが起きます。
こういうときは、困った漫画家は「主人公自身も知らなかった秘密の力が発動する」なんてことでストーリーを進めたりするのですが、こういう、いかにもその場しのぎのような後付け設定を何度も作っていると、読者から馬鹿されます。そうならないために、基本設定をあらかじめ、よく考えずにむやみやたらと作っておくと、こんどは内容に矛盾が出てくる可能性があります。
そんなわけで、マンガの基本設定というのは、少なすぎてもだめですが、やたらと多いのもだめで、適当な数があるはずなのです。
数学の場合の公理系も同様です。
公理が少なすぎると、証明問題で使えるルールが足りなくなってしまい、先に進めなくなって、真偽が決定できなくなってしまう可能性があります。
そうならないために、よく考えずに、やたらと公理の数を増やすと、今度は矛盾が起きる可能性があります。
公理系を作ったときに、それが正しく作れているか。つまり完全かつ無矛盾にできているかをチェックする必要があるわけですが、マンガの例のように、実はこれは案外難しい問題なのです。
(実際に、ちょうどこの頃に集合論が出来てくるのですが、当初は公理がおかしくて、いろいろ矛盾(パラドクス)が起きてしまい、あわてて修正するなど、混乱が起きていました。)ヒルベルトらの数学者は、公理系が完全かつ無矛盾で出来ていることをどうすればチェックできるか研究したわけです。
その流れの中で、ゲーデルは「正しく出来ているかをチェックするも何も、そもそも完全性と無矛盾性は両立できない。公理系が無矛盾なら不完全である。」
ということを見つけてしまったわけです。この「公理系が無矛盾なら不完全である。」というのが第一不完全性定理と呼ばれているものです。
つまり、「無矛盾に出来ている公理系では、真であるとも偽であるとも決定できない命題が含まれてしまう」ということです。
(すべての命題が決定不可能というわけではありません。大部分は真偽決定可能ですが、一部真偽が決められない命題があるということです)さらにまずいことに、真偽が決められない命題の一つが「今考えている公理系は無矛盾である。これは正しいか、間違いか?」
という命題であることもわかりました。
つまり「公理系が、無矛盾であれば、自身の無矛盾性を証明できない」ということです。(第二不完全性定理)ただ、この場合は真偽が決定できない問題がわかりましたが、一般的には、具体的に真偽決定不能な命題はどういうものなのかは、この不完全性定理だけではわかりません。
不完全性定理は、ただ「真偽が決定できない問題がある」ということを述べるだけです。この定理の証明は、むちゃくちゃ難しくはないのですが、ゲーデル数とか、無限集合論とか、濃度とか、高校程度ではあまり使わない用語がたくさん出てくるので、それなりの勉強が必要です。