今回は「ゲーテルの不完全性定理」と情報の世界についてご紹介したいと思います。
個人的にはこういうたぐいの論理が好きなので取り上げます（笑）
数学界の「ザ・ベスト不完全性定理」がゲーテルのものだとするなら、
社会科学におけるザ・ベスト不完全性定理は「アローの一般不可能性定理」でしょう。
ゲーテルはアメリカの市民権を取得する時、
憲法の知識について予習をしているうちに米国が独裁政権になる理論的可能性に気づきます。
面接で「米国がドイツのようになることはありません」と言った担当者に対して、
「いいえ、私は米国がドイツのようになることを証明できます」と言い、
推薦者であったアインシュタインを慌てさせたと伝えられてます。
アローの不可能性定理はこうした民主主義国家の制度について、
本当に民主的な国家は制度上存在し得ないということを示した定理です。
こちらについても、多くの方には結論は「あ、そうなんだ」と思う程度かとは思いますが、
いつの機会にか取り上げたいと思います。
さて、ゲーテルの不完全性定理は実社会では意識することのない、
数学の基礎的な枠組みについて証明できない命題があるということを示した定理です。
「証明できない」ということを証明することができるというだけで、
私はうまくイメージすることはできないのですが、そういうものなのだそうです。
ゲーテルの第1不完全性定理
「自然数論を含む無矛盾な公理体系は不完全である」
ゲーテルの第2不完全性定理
「自然数論を含む無矛盾な公理体系の中では、その無矛盾性を証明できない」
ここでいうゲーテルの不完全性定理というのは数学が不完全であるという意味ではなく、
あくまで、「特定の形式体系Pにおいて真偽証明ができない命題が存在する」という意味です。
これまで勉強してきた様々な数学の公理や定理は証明することができましたよね。
これ自体が真っ向から否定されるということではなく、
単に、数学には証明できない命題が存在すると言うことを示していると考えて良いでしょう。
ここで「ゲーテルの頭はハゲーテル」という命題が偽である証明をします。
不明 – Familienalbum der Familie Gödel, Scan from Gianbruno Guerrerio, Kurt Gödel – Logische Paradoxien und mathematische Wahrheit, S.24, パブリック・ドメイン, リンクによる
問題を解くことと数学を考えることは違う
前提として数学の問題を解くということは、公理や定理を使って問題を証明することです。
実は私もこれまでそんなことを知らずに勉強してきました。
結果として数学に関してはだいぶ遠回りをしてしまったのですが、
今だから言えることとしては、算数や数学ができるようになるには、
「教科書に書かれている公理や定理を覚えて、適用できるようになる訓練をすることが最短」ということです。
数学が暗記の学問だというのは勉強ができる人の考え方です。
勉強ができる人というのは、本質的な疑問で自分の思考が止まる前に、
所与のものをうまく使ってパズルを解くのが得意な人たちのことです。
もし、子供に数学を教えるときは本質的な理解よりも、
「解ける楽しみ」を先に感じてもらってから、大学などで深く研究してくれるといいですね。
試験の数学はあくまで知識の確認なので、
理解するよりも、まず暗記しなければ解くことができないのです。
公理の世界は数学というより論理の哲学
ここで、公理というのは最も基礎的な前提条件です。
例えば「数1は自然数だ」という公理があります。
これは誰からみてもそう定義する以上はそうなので公理です。
一方で定理は公理から導かれる条件です。
「三平方の定理」は距離の公理を前提としたときに証明することのできる定理です。
つまり、すべての定理は公理から生まれます。
命題を証明するためには公理からスタートするのです。
それでは公理からスタートすれば、数学全体の原理を証明することはできるのでしょうか。
「できません」というのがゲーテルの不完全性定理の証明です。
例えば「私は嘘をついています」という文章は、自然に読めばその人は嘘つきなわけですが、
この文章が正しいとすると、嘘を含んでいるので偽となるはずです。
それを真とする仮説を立てると、それが偽だという矛盾を含みます。
論理学では真か偽かですから前提が矛盾するとするとこの文章は偽となります。
しかし、逆に前提とする「私は嘘をついています」を偽とすると、
そこで言っている内容は真ではないということになります。
それでは矛盾するので結論として真ということになります。
つまり、真でもあり偽でもあるのです。
命題の真偽を証明することで決定しようとしたらできなくなってしまったわけです。
文章で記述するとちょっとどころかかなりわかりにくいですね。
コンピューター的に考えてみましょう！
嘘つきのパラドクス論理構造の形式的記述
嘘つきのパラドクスは自己言及しようとすると生じるパラドクスです。
「世の中は正義か悪しかない」みたいな考え方を二元論的といいますが、
数学に置いては真と偽という真理値で表されます。
コンピューターでは「True」と「False」という言葉を使いますね。
例えば先程の「私は嘘をついています」という文章を（A）とします。
これをTrueとするならば、Aはすべて真である必要があります。
ただ、偽を含んでいる文Aを真とするというのは矛盾しています。
我々はこういう頭の痛くなるような論理をうまく流しています。
あたりまえだろうと思うかもしれないのですが、
「5」という値をTrueとするとして、なんらかの計算で5という値が出た時は、
Trueである必要がありますよね。というよりTrueですね。
それ以外に解釈のしようが無いくらい厳密に解が出ます。
つまり矛盾してないのです。
しかし、自己言及する場合は先程のAをTrueとすると、
A自体に偽を含んでしまっているのでFalseになってしまいます。
この文章（B）を偽だとしてみると以下のように表現できます。
$$”B=False”$$
そしてBが偽であると述べている文（C）は以下のように表現できます。
$$”C=’B=False'”$$
嘘つきのパラドクスを（A）とするとAは偽なので、
$$”A=’A=False'”$$
となります。しかし、コンピューター的には当然A=Falseですから、
“Not A”ということになり、結果として上の式は矛盾するので解くことができません。
でもこうして改めて形式的に見てみると「＝」の意味合いも少し違うように思いますし、
文章の内部の偽と文章全体の偽も区別されるべきなのではないかと思いました。（直感ですが）
確かにパラドクスなのですが、「私は嘘をついています」と言われたら、
ほとんどのひとはパラドクスに気づく前に「この人は嘘付いてるんだ」と思いますよね。
つまり文章全体を真と信じて、文章の中身のパラドクスについては無視するように思います。
嘘をついているという嘘をついている…みたいなマトリョーシカ的に考えなくて、
現実的にはとりあえず本人は真であるということを前提として、
計算をループさせないように本能的になってるようです。
これぞ、ハーバート・サイモンの限定合理性の源とも言えるかもしれませんね。
コンピューターとどの辺りが関係するのか？
こうした論理はベン図のようなものを書いて考えたことがある人も多いと思います。
コンピューターでもORやAND、∧や∨といった演算子を扱うので親しみはあるでしょう。
ただ、この不完全性定理自体はあくまでコンピューターの存在を破壊するものでも、
その可能性を閉ざすものでもありません。
特に面白いところはその知性を様々な分野に影響を与えたこと。
そして、彼に影響を受けた周囲にいた天才的な研究仲間だったと言えます。
例えば、コンピューターの父とも称されるアラン・チューリングは、
ゲーテルの不完全性定理に影響を受けたと言われています。
現代のコンピューターはチューリング完全と言われます。
チューリングマシンを、可能な範囲で実現・具体化（実装）するもので、
記憶装置を仮に、必要であれば必要なだけ無制限に追加できるものとすれば、
計算模型として見た場合チューリング完全とみなせることになるということです。
当たり前のように思えますが、計算をするための機械として、
前提となる体系に矛盾が含まれていたら計算が間違ったものになる可能性があります。
チューリング完全なコンピューターはこうした矛盾がないことが前提なのです。
同じく、偉大な数学者であるフォン・ノイマンという天才は、
オペレーションズ・リサーチやゲーム理論など、
現代の様々な役立つ数学を生み出した数学者です。
彼もまたゲーテルの不完全性定理には驚いたと言われています。
集合論のパラドクスは当時から知られていましたが、
数学ですべては記述できるとノイマンもまた師であるヒルベルトも考えていたからです。
話は脱線しますが、フォン・ノイマンはマンハッタン計画にも関わっていた事で有名です。
当時米国はドイツから逃れる研究者の知能を借りて、
戦争に勝つために数学的に、物理的に、統計的に計算して、
どのように戦ったら良いのかを考えさせました。
そして天才アインシュタインも出てきます。
前述の通りアインシュタインとゲーテルについても親交があったようですね。
完全無欠の数学体系は無いけれど物理はもう少し？
そもそも、なんでこんな定理が生まれたのかと言うと、
もともとはニュートンが「プリンキピア」で自然界の原理について、
その全体を体系化したわけです。これがニュートンが構築した物理体系、
すなわち、ニュートン力学（単に力学）と呼ばれるものです。
同じようなことが数学でもできるんじゃないか！
そう考えたのがラッセルとホワイトヘッドの「プリンキピア・マテマティカ」です。
彼らは公理と推論規則から数学全体を記述しようと試みたのです。
そのために、論理学という記号で置き換える方法を使っていきました。
一番最初に書いたとおり、ゲーテルは確かにこうした試みを打ち砕いたわけですが、
実際、数学の殆どは集合の言葉で形式化できます。
確かに、ゲーテルが指摘したように証明できないものもあるのですが、
現実的には無矛盾性が担保されている数学でほとんどの仕事ができます。
そういうこともあり、完全無欠な数学の体系をつくるというよりは、
現在は数学の一部がどのような特定の形式体系で、
形式化することが可能であるかについての研究が主流となっているようです。
物理においても力学から相対性、そして量子力学へと、
すべての原理が体系化されているわけではありません。（少なくとも現時点では）
そのあたりは「万物の理論」について調べてみると良いかもしれません。
ただ、ホーキング博士はこうも言っていました。
「最善のシナリオとは完全に正しい統一理論が完成することである。
最悪のシナリオとは間違った統一理論が完成することである。
次善のシナリオとは完全で正しい理論が完成しないことがわかることである。」
まとめ
ゲーテルとコンピューターについて語ろうとしたらあまり書くことがなく、
ゲーテルを取り巻く人の紹介と不完全性定理の形式的記述について、
面白いところだけご紹介する記事になってしまいました。
でも、最後に触れたように今の科学技術の基礎となる考え方が、
ゲーテルを始め世界大戦中にポンポンと出てきたという事実は不思議ですよね。
戦争と科学技術との関係を改めて考えてしまいました。
世の中が二元論的に切り分けることのできない世界であることは十分知っているはず、
でも、人間の不完全性については誰も証明できないのでしょうかね。