ゲーデルの証明の仕組み

1931 年、オーストリアの論理学者クルト・ゲーデルは、おそらく歴史上最も驚くべき知的成果の一つを成し遂げました。

当時の数学者たちは、数学の確固たる基盤、つまり、一貫していて決して矛盾を生じず、完全で、あらゆる数学的真理の構成要素として機能する一連の基本的な数学的事実、つまり公理を求めていました。

しかし、ゲーデルがわずか25歳で発表した衝撃的な不完全性定理によって、その夢は打ち砕かれた。彼は、数学の基礎となり得る公理の集合はどれも必然的に不完全であることを証明した。つまり、それらの公理では証明できない数に関する真実が必ず存在するということだ。また、いかなる公理の集合も、それ自体の整合性を証明できないことも示した。

彼の不完全性定理は、万物に関する数学理論は存在し得ず、証明可能なことと真実の統一も不可能であることを意味した。数学者が証明できるものは、出発点となる仮定に依存するものであり、すべての答えの源泉となる根本的な真実に依存するものではない。

ゲーデルの発見から89年、数学者たちはまさに彼の定理が予言していたような、答えられない問いに遭遇してきた。例えば、ゲーデル自身は、無限の大きさに関する連続体仮説が決定不可能であることの証明に貢献した。また、ランダムな入力を与えたコンピュータプログラムが永遠に実行されるか、最終的に停止するかを問う停止問題も同様である。決定不可能な問いは物理学にも現れており、ゲーデルの不完全性は数学だけでなく、何らかの理解されていない形で現実にも影響を与えていることを示唆している。

ゲーデルがどのようにして定理を証明したかを、簡略化して簡単に説明します。

ゲーデル数

ゲーデルの主な手法は、公理系に関する言明を、その系内の言明、つまり数に関する言明に写像することだった。この写像によって、公理系は自身について論理的に語ることができる。

このプロセスの最初のステップは、あらゆる可能な数学的記述または一連の記述を、ゲーデル数と呼ばれる一意の数値にマッピングすることです。

アーネスト・ネーゲルとジェームズ・ニューマンが1958年に著した『ゲーデルの証明』で提示した、ゲーデルの図式を若干改変したバージョンは、一連の基本公理を表現するための語彙となる12個の基本記号から始まります。例えば、何かが存在するという命題は記号∃で表され、加算は+で表されます。重要なのは、「後続」を表す記号sが数値を指定する方法を与えていることです。例えば、ss0は2を表します。

これらの 12 個のシンボルには、ゲーデル数 1 から 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つの式が同じゲーデル数になることが決してないからです。ゲーデル数は整数であり、整数を素因数分解する方法は1つしかありません。したがって、243,000,000を素因数分解できるのは2 ⁶ × 3 ⁵ × 5 ⁶のみであり、ゲーデル数を解読する方法は0 = 0という式のみであることを意味します。

ゲーデルはさらに一歩進んだ。数学の証明は式の列から成り立つ。そこでゲーデルは、すべての式の列に固有のゲーデル数を与えた。この場合、彼は先ほどと同様に素数のリストから始める。2、3、5…と。そして、それぞれの素数を、列の同じ位置にある式のゲーデル数（例えば、0 = 0が最初に来る場合は2の^243,000,000 × …）で乗じ、すべてを掛け合わせる。

メタ数学の算術化

本当の恩恵は、メタ数学的ステートメントと呼ばれる算術式に関するステートメントさえも、それ自体がゲーデル数を持つ式に変換できることです。

まず、「ゼロはゼロではない」という意味の式 ∼(0 = 0) を考えてみましょう。この式は明らかに誤りです。しかし、ゲーデル数を持ちます。2の1乗（記号 ∼ のゲーデル数）に3の8乗（「開き括弧」記号のゲーデル数）を掛け合わせると、2¹ × 3 ⁸ × 5 ⁶ × 7 ⁵ × 11 ⁶ × 13 ⁹となります。

すべての式に対して、たとえ誤った式であってもゲーデル数を生成できるため、ゲーデル数について話すことでこれらの式について合理的に話すことができます。

「式 ∼(0 = 0) の最初の記号はチルダである」という記述を考えてみましょう。 ∼(0 = 0) についてのこの (真の) メタ数学的記述は、式のゲーデル数についての記述、つまり、その最初の指数が 1 であり、チルダのゲーデル数である、という記述に変換されます。 言い換えると、この記述は、 2 ¹ × 3 ⁸ × 5 ⁶ × ^{7 5} × 11 6 × 13 ⁹には 2 の因数が 1 つしかないことを示しています。 ∼(0 = 0) がチルダ以外の記号で始まっていたとしたら、そのゲーデル数は 2 の因数を少なくとも 2 つ持つことになります。 つまり、より正確には、 2 は 2 ¹ × 3 ⁸ × 5 6 × 7 ⁵ × ¹¹ 6 × 13 9の因数ですが、 2 2 は因数ではありません。

最後の文を、基本記号を使って書き表すことができる正確な算術式に変換することができます。* (記事の最後までスクロールしてご覧ください。) もちろんこの式にはゲーデル数があり、その記号を素数の累乗にマッピングすることで計算できます。

この例は、「ゲーデルの発見の核心にある、非常に一般的で深い洞察を例示している。つまり、長い記号の連鎖の印刷特性は、大きな整数の素因数分解の特性について話すことで、間接的だが完全に正確な方法で話すことができる」とネーゲルとニューマンは書いている。

「ゲーデル数kの式を証明するゲーデル数xの式の列が存在する」、つまり「ゲーデル数kの式は証明できる」というメタ数学的命題も記号化可能である。この種の命題を「算術化」する能力が、クーデターの舞台を整えた。

G自体

ゲーデルのさらなる洞察力は、数式自体に数式自身のゲーデル数を代入することができ、それが終わりのないトラブルにつながるということでした。

置換がどのように機能するかを確認するために、式 (∃ x )( x = sy ) を考えてみましょう。(これは「 yの後継となる変数xが存在する」、つまり「yには後継変数がある」という意味です。) すべての式と同様に、この式にもゲーデル数、つまりmと呼ぶ大きな整数があります。

ここで、式に記号yの代わりにmを導入してみましょう。これにより新しい式 (∃ 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の式を、ゲーデル数17の記号がある場所にnを代入して得られる式のゲーデル数です。そして、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 8 × 5 6 × 7 5 × 11 6 × 13 9に等しい整数xが存在し、 xの 4 倍が 2¹ × 3 8 × 5 6 × 7 5 × 11 6 × 13 9に等しい整数xは存在しません。」対応する式は次のとおりです。

(∃ x )( x × ss0 = sss … sss0 ) ⋅ ~(∃ x )( x × ssss0 = sss … sss0 )

ここで、sss … sss0 は後続記号sの2¹ × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 個のコピーを表します。^記号⋅^は「^and」^を意味^し、基本語彙におけるより長い表現の省略形です。p ⋅ q は∼(∼ p ∨ ∼ q ) を表します。

オリジナルストーリーは、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得て転載されました。

WIREDのその他の素晴らしい記事

• マスクが着用不要から必需品になった経緯
• 私たちが夢中になるYouTubeチャンネル13選
• テクノロジーは「マスター」と「スレーブ」というレッテルの使用に直面する
• ポーカーと不確実性の心理学
• コロナに追いつく ― あるいは、なぜウイルスが勝利しているのか
• 👁 セラピストが登場。チャットボットアプリです。さらに、最新のAIニュースもお届けします
• 💻 Gearチームのお気に入りのノートパソコン、キーボード、タイピングの代替品、ノイズキャンセリングヘッドホンで仕事の効率をアップさせましょう