「不完全性定理」

【まえがき】

　このページでは、 正直者のパラドクスを用いた日常言語による不完全性定理の証明を行います。 正直者のパラドクスは、「私は正直者です」という文の真偽を考えると起こります。 もし、「私」が正直者であれば、この文は真となって何の矛盾もありません。 しかし、「私」が嘘つきだったとしても、 嘘つきが自分を正直者と嘘をつくことに何の矛盾もありません。 つまり、「私は正直者です」という文は、真と考えても偽と考えても矛盾せず、 どちらか分からないのです。ここでは、「私」が健全であるなら、 「私は正直者です」が証明も反証もできないこと、 すなわち第一不完全性定理を証明し、それを用いて第二不完全性定理も証明します。

　ただし、ここで証明する第一不完全性定理は、 無矛盾ならば不完全という形ではなく、健全なら不完全という形です。 また、第二不完全性定理は、 無矛盾なら無矛盾であることを証明できないという形ではなく、 健全なら健全であることを証明できないという形の定理です。 健全性とは無矛盾性より強い性質で、証明できるなら真という性質です。 健全なら無矛盾ですが、無矛盾なら健全とは限りません。 しかし、健全性の成り立たない理論は、たとえ無矛盾だとしても使い物にならないので、 論理の信頼性を議論するという意味では、この形の定理の方が重要です。

【準備】

　まず、いくつか準備をしましょう。 「私」という代名詞と正直者という概念にはいくつかの解釈があるのですが、 ここでは第二不完全性定理を証明するのに必要な解釈を採用します。 以下では「私」は人であるかのように書きますが、 実際には公理系を指すと思ってもらうと分かりやすいかもしれません。 想定するのは日常言語を交えた自然数論の公理系です。 自然数論程度の記述能力があれば、 「私は正直者です」という概念を表現できるはずです。 これは厳密には証明が必要なことですが、ここでは認めてしまいましょう。

　次に、「私」とは正直者かあるいは嘘つきのことです。 正直者でも嘘つきでもない人はこの世界にはいません。 正直者とは自然数論の真なる文のみを発言する人のことです。 正直者が発言できる文のことを正直者の発言可能文と呼ぶことにします。また、 嘘つきとは自然数論の偽なる文のみを発言する人にことです。 嘘つきが発言できる文のことを嘘つきの発言可能文と呼ぶことにします。 正直者の発言可能文のうち、証明可能な文のことを定理と呼びます。 嘘つきの発言可能文のうち、反証可能な文のことを反定理と呼びます。 明らかに、 定理は正直者の発言可能文の部分集合であり、 反定理は嘘つきの発言可能文の部分集合です。

　また、定理と反定理の間には以下の関係があります。 もし、命題 A が定理ならば、not A は反定理です。 もし、命題 A が反定理ならば、not A は定理です。 さらに、次の条件が成り立つとします。 正直者は正直者の発言可能文の全てを発言する必要はありません。 定理の全てを発言すれば十分です。 嘘つきは嘘つきの発言可能文の全てを発言する必要はありません。 反定理の全てを発言すれば十分です。 つまり、どちらにも黙秘権があります。 以上で準備は終わりです。

【第一不完全性定理】

　これから第一不完全性定理の証明を始めます。 まず、「私は正直者です」が定理であると仮定します。 すると、「私は正直者ではない」が反定理になるはずです。 しかし、「私は正直者ではない」は嘘つきの発言可能文ではありません。 反定理は嘘つきの発言可能文の部分集合なので、 「私は正直者ではない」は反定理ではありません。 これは矛盾なので、「私は正直者です」は定理ではありません。

　次に、「私は正直者です」が反定理であると仮定します。 すると、「私は正直者ではない」が定理になるはずです。 しかし、「私は正直者ではない」は正直者の発言可能文ではありません。 定理は正直者の発言可能文の部分集合なので、 「私は正直者ではない」は定理ではありません。 これは矛盾なので、「私は正直者です」は反定理ではありません。

　「私は正直者です」は定理でも反定理でもないので、 証明することも反証することもできません。 これで第一不完全性定理が証明できました。ただし、「私」が矛盾する場合、 つまり「私」が従っている自然数論が矛盾する場合は、 全ての命題が証明かつ反証できるので、上記の証明は成立しなくなります。 したがって、上記の証明には、「私」は無矛盾であるという条件が必要です。 実際には、正直者という概念を表現するのに、より強い健全性が必要です。 これは、「私」は正直者か嘘つきかのどちらかで、 正直者でも嘘つきでもないという状態がないという条件と同値です。

【第二不完全性定理】

　これから第二不完全性定理の証明を始めます。「私は正直者です」が真だとします。 すると、「私」の発言は全て正しいことになります。 ここで、「私」の定理を任意に１つ選び命題 A とすると、 定理は正直者の発言可能文の部分集合なのですから、A は必ず真になります。 定理は証明できる文のことなので、これは証明できるなら真ということです。 よって、「私は正直者です」という文は健全性を表す文です。

　上記、第一不完全性定理の証明により、 「私は正直者です」は証明も反証もできませんので、 健全性は証明も反証もできません。これで第二不完全性定理が証明できました。

【あとがき】

　このページでは正直者のパラドクスを用いて、 第一不完全性定理と第二不完全性定理をきわめて簡単に証明してしまいました。 特に難しい数式や概念を用いているわけではないので、 たぶん間違いはないと思いますが、証明した当の本人ですらマジか？ という心境です。何かとんでもない見落としがある可能性もあるので、 参考にする人は十分に検証してくださいね。

【追記】

　その後詳しく考えて、何でこんなに簡単に不完全性定理が証明できるのか、 そのカラクリが分かりました。日常言語では「私」という代名詞が、 正直者も嘘つきも指すことができます。しかし、数学の言語では、 正直者な私と嘘つきな私を使い分けてやらねばなりません。 つまり、「私は正直者です」という命題を論理式に書き換えてやると、 正直者バージョンと嘘つきバージョンの２通りの論理式ができるということです。 なるほど、それだと数学の言語では上記の証明は通りませんね。 そのほか、無矛盾性と健全性の違いなども影響しているようです。

　この教訓は、日常言語の表現力は数学の言語より強力で、 日常言語では簡単に証明できることでも、 数学の言語で簡単に証明できるとは限らないということですかね。 漠然とした感想ですが、文脈依存と文脈自由の違い等が原因ではないかと思います。

　それにしてもこのネタは危険ですね。 私自身私にまんまとだまされてしまいましたが、 素人をけむに巻くにはうってつけのネタですね。コワいコワい。