野崎 昭弘
筑摩書房 (2006/05)
売り上げランキング: 17238
入門!論理学を読んでから、次は不完全性定理だ、と心に決めておりました。そんな折、書店で本書を見かけまして、「新書で不完全性定理の本があるなんて、ラッキー」という気軽な気持ちで購入しました。
で、これが、実によい本だったのです。丁寧に、わかりやすく書かれています。わかりやすく、とは言っても、私の読解力では「一読してたちどころに」とはいきませんでしたので、三読、四読しました。読むたびに「あー、そういうことを言っているのか」と、少しずつ薄皮をはいでいくような気分でした。
「第1不完全性定理:自然数論を含む帰納的に記述できる公理系が、無矛盾であれば、証明も反証もできない命題が存在する。(ゲーデルの不完全性定理 - Wikipedia)」
ようやく、この文章の意味がわかりました。論理学の上に数学を位置づけようとしたが、厳密にはできなかった、ということです。
「(1)証明」も「(2)反証」もできない命題というのは、「この命題は証明できない」という命題です。これが証明できるとすれば←(1)、「証明できない」と矛盾です。そして「証明できない」が正しいとして証明しようとしても←(2)、正しいとしても、正しいからこそ、「証明することができない」ということです。
自然数論を含む公理系では、そういう命題が存在してしまう、ということです。
ここで、自己言及(self-reference)というのがキーになってくるわけです。
次の2つはパラドックス。
・新約聖書:「クレタ人はうそつきだ」とクレタ人が言った。は矛盾。
・集合論:「集合N:“自分自身を要素として含まない集合”すべての集合」は、集合Nに含まれるのか?実は、含まれるとしても含まれないとしても矛盾。
で、この次の2つはパラドックスではなく、特に停止問題は、ゲーデルの不完全性定理と同様の話。
・相対主義:「いかなる命題も、絶対に正しいということはない」という命題も正しいとはいえないのではないか。→絶対主義的には相対主義を規定できない。
・プログラム停止問題:「あるプログラムが一定時間に停止するかどうかが分かるプログラム」が存在するとしたら、実は「このプログラムが一定時間に停止することがわかったら停止するな、というプログラム」が存在するので、矛盾。だから一定時間に停止するかどうかが分かるプログラムは存在しない。
以前、アルゴリズムを勉強しようと思ったとき、「再帰」の処理がいまいち理解できていませんでした。これでようやっと、読む準備ができたかな?
---
ここのところ、空いた時間はずっとこの「不完全性定理」のことを考えていました。口の中で飴を溶かすように、すこしづつ、すこしづつ理解をしていく過程が楽しいです。まだまだ、飴は溶けきっていませんけどね。
最近のコメント