ゲーデルの証明の仕組み
How Gödel's Proof Works (quantamagazine.org)
要約
ゲーデルの不完全性定理は、数学の「すべてを網羅する理論」という探求を破壊しました。この記事では、ゲーデルがどのようにして、いかなる公理系も不完全であり、自身の無矛盾性を証明できないことを証明したのか、その仕組みを解説します。この発見は、数学だけでなく現実世界にも影響を与えています。
全文翻訳
ゲーデルの証明はどのように機能するか
1931年、オーストリアの論理学者クルト・ゲーデルは、歴史上最も驚くべき知的成果の一つを成し遂げました。
当時の数学者たちは、数学のための確固たる基盤、すなわち、矛盾を生じない「無矛盾」であり、かつすべての数学的真理の構成要素となる「完全」な基本的事実、あるいは公理の集合を求めていました。
しかし、25歳にして発表されたゲーデルの衝撃的な不完全性定理は、その夢を打ち砕きました。彼は、数学の基礎として考えうるいかなる公理系も必然的に不完全であり、それらの公理では証明できない真の事実が常に存在することを証明しました。また、いかなる公理系も自身の無矛盾性を証明できないことも示しました。
彼の不完全性定理は、すべてを説明する数学的理論、証明可能なものと真実であるものの統一は存在しえないことを意味しました。数学者が証明できることは、すべての答えの源泉となる根本的な真実からではなく、彼らの出発点となる仮定に依存するのです。
ゲーデルの発見から89年が経過した現在でも、数学者たちは彼の定理が予言したまさにその種の証明不可能な問題に遭遇しています。例えば、ゲーデル自身が、無限のサイズに関する「連続体仮説」が決定不能であること、そしてコンピュータプログラムが無限に実行し続けるか最終的に停止するかを問う「停止性問題」も同様に決定不能であることを確立するのに貢献しました。決定不能な問題は、「物理学においても生じており」、ゲーデル的不完全性が数学だけでなく、ある不明瞭な方法で現実にも影響を与えていることを示唆しています。
ここでは、ゲーデルがどのようにして彼の定理を証明したのかを、簡略化された非公式な解説で示します。
ゲーデル数
ゲーデルの主な手腕は、公理系に関する命題を、その公理系内の命題、すなわち数に関する命題にマッピングすることでした。このマッピングにより、公理系はそれ自身について論理的に語ることができるようになります。
このプロセスの最初のステップは、可能なあらゆる数学的命題、あるいは一連の命題を、ゲーデル数と呼ばれる一意の数にマッピングすることです。
アーネスト・ネイゲルとジェームズ・ニューマンが1958年の著書『ゲーデルの証明』で提示した、ゲーデルのスキームのわずかに改変されたバージョンは、基本公理の集合を表現するための語彙として機能する12個の基本的な記号から始まります。例えば、「存在する」という命題は記号∃で表現でき、加算は+で表現できます。重要なのは、「後者」を意味する記号sであり、数を示す方法を提供します。例えば、ss0は2を指します。
これらの12個の記号には、1から12までのゲーデル数が割り当てられます。
| 定数記号 | ゲーデル数 | 通常の意味 |
| ~ | 1 | 非(否定) |
| ∨ | 2 | または |
| ⊃ | 3 | ならば |
| ∃ | 4 | 存在する |
| = | 5 | 等しい |
| 0 | 6 | ゼロ |
| s | 7 | の後者 |
| ( | 8 | 句読点 |
| ) | 9 | 句読点 |
| , | 10 | 句読点 |
| + | 11 | プラス |
| × | 12 | 掛ける |
次に、変数(x, y, zから始まる)を表す文字には、12より大きい素数(すなわち13, 17, 19, …)がマッピングされます。
次に、これらの記号と変数の任意の組み合わせ、つまり構築可能なあらゆる算術的公式または公式のシーケンスが、それ自身のゲーデル数を持つことになります。
例えば、0 = 0 を考えてみましょう。この公式の3つの記号は、ゲーデル数6、5、6に対応します。ゲーデルは、この3つの数のシーケンスを、他のどのシーケンスも生成しない単一の一意の数に変換する必要があります。これを行うために、彼は最初の3つの素数(2, 3, 5)を取り、それぞれをシーケンスの同じ位置にある記号のゲーデル数にべき乗し、それらを掛け合わせます。したがって、0 = 0 は 2⁶ × 3⁵ × 5⁶、つまり243,000,000になります。
このマッピングが機能するのは、2つの公式が同じゲーデル数を持つことが決してないからです。ゲーデル数は整数であり、整数は素因数分解が一意に定まります。したがって、243,000,000の素因数分解は 2⁶ × 3⁵ × 5⁶ のみであり、ゲーデル数をデコードする方法は1つしかないことを意味します:公式 0 = 0 です。
ゲーデルはさらに一歩進みました。数学的証明は公式のシーケンスで構成されます。そこでゲーデルは、公式のシーケンスのそれぞれに一意のゲーデル数を与えました。この場合、彼は以前と同じように素数のリスト(2, 3, 5など)から始めます。次に、各素数をシーケンスの同じ位置にある公式のゲーデル数にべき乗し(例えば、0 = 0 が最初に来る場合、2²⁴³⁰⁰⁰⁰⁰⁰ × …)、すべてを掛け合わせます。
メタ数学の算術化
真の利点は、算術公式に関するメタ数学的命題でさえ、それ自体が独自のゲーデル数を持つ公式に翻訳できることです。
まず、~(0 = 0) という公式を考えてみましょう。「ゼロはゼロに等しくない」という意味です。この公式は明らかに偽です。それにもかかわらず、それはゲーデル数を持っています:2を1(記号~のゲーデル数)のべき乗、3を8(「開き括弧」記号のゲーデル数)のべき乗で掛けたもの、そしてそれ以降、2¹ × 3⁸ × 5⁶ × 7⁵ × 11⁶ × 13⁹ を生成します。
すべての公式、偽の公式でさえゲーデル数を生成できるため、それらのゲーデル数について語ることで、これらの公式について意味のある議論ができます。
「~(0 = 0) の最初の記号はチルダである」という命題を考えてみましょう。これは(真の)メタ数学的命題であり、公式のゲーデル数に関する命題に翻訳されます。すなわち、その最初の指数がチルダのゲーデル数である1であるということです。言い換えれば、私たちの命題は、2¹ × 3⁸ × 5⁶ × 7⁵ × 11⁶ × 13⁹ が2の単一の因数のみを持つことを述べています。もし~(0 = 0) がチルダ以外の記号で始まっていたら、そのゲーデル数は少なくとも2つの2の因数を持つでしょう。したがって、より正確には、2は2¹ × 3⁸ × 5⁶ × 7⁵ × 11⁶ × 13⁹ の因数ですが、2²は因数ではありません。
最後の文を、基本的な記号を使って書き留めることができる正確な算術公式に変換できます。この公式はもちろんゲーデル数を持ち、その記号を素数のべき乗にマッピングすることで計算できます。
この例は、ネイゲルとニューマンが書いたように、「ゲーデルの発見の中心にある非常に一般的で深い洞察を例示しています。長い記号の連なりのタイプ的な性質は、大きな整数の素因数分解の性質について語ることによって、間接的ではあるが完全に正確な方法で語ることができます。」
「ゲーデル数xを持つ公式のシーケンスが存在し、ゲーデル数kを持つ公式を証明する」というメタ数学的命題、つまり短く言えば「ゲーデル数kを持つ公式は証明可能である」という命題も、記号への変換が可能です。この種の命題を「算術化」する能力が、この偉業の舞台を整えました。
G自体
ゲーデルのさらなる洞察は、公式自身のゲーデル数を公式自体に代入できることであり、それが無限のトラブルを引き起こしました。
代入がどのように機能するかを見るために、(∃x)(x = sy) という公式を考えてみましょう。(これは「変数xが存在し、それはyの後者である」と読みます。つまり、短く言えば「yには後者が存在する」です。)すべての公式と同様に、それはゲーデル数、つまりm*と呼ぶ大きな整数を持ちます。
ここで、mをy記号の代わりに公式に導入します。これにより、新しい公式 (∃x)(x = sm) が形成されます。これは「mには後者が存在する」という意味です。この公式のゲーデル数を何と呼ぶべきでしょうか?伝えるべき情報は3つあります:私たちはゲーデル数mを持つ公式から始めました。その公式で、y記号の代わりにmを代入しました。そして、先に導入したマッピングスキームによれば、y*記号はゲーデル数17を持ちます。そこで、新しい公式のゲーデル数を sub(m, m, 17) としましょう。
代入はゲーデルの証明の核心を形成します。
彼は、「ゲーデル数 sub(y, y, 17) を持つ公式は証明できない」というようなメタ数学的命題を考慮しました。私たちが学んだ表記法を思い出すと、ゲーデル数 sub(y, y, 17) を持つ公式は、ゲーデル数yを持つ公式を取り、yの代わりにその変数を、ゲーデル数17を持つ記号(すなわちyがある場所)のどこにでも代入することによって得られる公式です。
物事は奇妙になってきていますが、それでも、私たちのメタ数学的命題、「ゲーデル数 sub(y, y, 17) を持つ公式は証明できない」は、一意のゲーデル数を持つ公式に翻訳されることは確かです。それをnと呼びましょう。
最後に、もう一度代入を行います:ゲーデルは、前の公式のyがある場所にnという数を代入することによって新しい公式を作成します。その新しい公式は、「ゲーデル数 sub(n, n, 17) を持つ公式は証明できない」と読みます。この新しい公式をGと呼びましょう。
当然、Gはゲーデル数を持っています。その値は何でしょうか?見てみると、それは sub(n, n, 17) でなければなりません。定義によれば、sub(n, n, 17) は、ゲーデル数nを持つ公式を取り、nをゲーデル数17を持つ記号のどこにでも代入することによって得られる公式のゲーデル数です。そして、Gはまさにこの公式なのです!素因数分解の一意性のため、Gが言及している公式はG自身に他ならないことがわかります。
Gは、それ自身が証明できないと主張しています。
しかし、Gは証明できるでしょうか?もしそうなら、それはゲーデル数 sub(n, n, 17) を持つ公式を証明する公式のシーケンスが存在することを意味します。しかし、それはGの反対であり、そのような証明は存在しないと述べています。反対の命題、Gと~Gは、無矛盾な公理系では両方とも真であることはできません。したがって、Gの真実は決定不能でなければなりません。
しかし、Gは決定不能ですが、明らかに真です。Gは「ゲーデル数 sub(n, n, 17) を持つ公式は証明できない」と述べており、まさにそれがケースであると判明したのです!Gは真でありながら、それを構築するために使用された公理系内では決定不能であるため、そのシステムは不完全です。
余分な公理を仮定してGを証明し、パラドックスを解決できると思うかもしれません。しかし、それはできません。ゲーデルは、拡張された公理系が、以前の同様の設計図に従って、新しい、真の公式G'(新しい、拡張されたシステム内では証明できない)を構築することを可能にすることを示しました。完全な数学的システムを目指す中で、あなたは決して自分の尻尾を捕らえることはできません。
無矛盾性の証明なし
公理系が無矛盾であるならば、それは不完全である、ということを学びました。それがゲーデルの第一不完全性定理です。第二の定理、すなわちいかなる公理系も自身の無矛盾性を証明できない、ということも容易に導かれます。
公理系がいかなる矛盾も生じないと証明できるとしたら、それは何を意味するでしょうか?それは、これらの公理から構築された公式のシーケンスが存在し、「この公理系は無矛盾である」という意味のメタ数学的公式を証明することを意味します。第一定理によれば、この公理系は必然的に不完全であることになります。
しかし、「公理系は不完全である」ということは、「証明できない真の公式が存在する」ということと同じです。この命題は、私たちの公式Gと同等です。そして、公理系がGを証明できないことはわかっています。
したがって、ゲーデルは背理法による証明を作成しました:もし公理系が自身の無矛盾性を証明できるなら、私たちはGを証明できるでしょう。しかし、私たちはできません。したがって、いかなる公理系も自身の無矛盾性を証明することはできません。
ゲーデルの証明は、無矛盾で完全な数学的システムを求める探求を終わらせました。不完全性の意味は「まだ完全に解明されていない」と、ネイゲルとニューマンは1958年に書きました。それは今日でも真実です。
- 興味のある方のために、その命題は次のように述べられています:「x × 2 = 2¹ × 3⁸ × 5⁶ × 7⁵ × 11⁶ × 13⁹ となる整数xが存在し、かつx × 4 = 2¹ × 3⁸ × 5⁶ × 7⁵ × 11⁶ × 13⁹ となる整数xは存在しない。」対応する公式は次のとおりです。
(∃x)(x × ss0 = sss … sss0) ⋅ ~(∃x)(x × ssss0 = sss … sss0)
ここで、sss … sss0 は 2¹ × 3⁸ × 5⁶ × 7⁵ × 11⁶ × 13⁹ 個の後者記号sを表します。記号p ⋅ q は「かつ」を意味し、基本的な語彙のより長い表現の略記です:p ⋅ q は ~(~p ∨ ~q) を表します。 [記事に戻る]
この記事は Wired.comに再掲載されました。