ゲーデルの証明の仕組み

1931年、オーストリアの論理学者クルト・ゲーデルは、歴史上最も衝撃的な知的業績の一つを成し遂げました。

当時の数学者たちは、数学の強固な基礎を求めていました。それは、基本的な数学的事実の集合、すなわち公理であり、矛盾を生まない一貫性と、すべての数学的真理の構成要素としての完全性を兼ね備えたものでした。 ゲーデルは、数学の基礎となりうる公理の集合は、必然的に不完全なものとなることを証明しました。つまり、それらの公理では証明できない数に関する真の事実が常に存在するのです。

彼の不完全性定理は、数学的な万物の理論が存在しないことを意味し、証明可能なことと真のことを統一することはできません。

ゲーデルが不完全性定理を発見してから89年間、数学者たちは、彼の定理が予告していたような答えのない問題に遭遇してきました。 例えば、ゲーデルは、無限の大きさに関する連続体仮説が決定不可能であることを明らかにしました。また、ランダムな入力を与えられたコンピュータプログラムが永遠に実行されるか、あるいは最終的に停止するかを問うハルティング問題も同様です。

ここでは、ゲーデルが自分の定理をどのように証明したかを、簡略化して非公式に説明します。

ゲーデルの番号付け

ゲーデルの主な手法は、公理系に関する文を公理系内の文、つまり数に関する文にマッピングすることでした。

このプロセスの最初のステップは、ありとあらゆる数学的な文や一連の文を、ゲーデル数と呼ばれる一意の数に対応させることです。

アーネスト・ネーゲルとジェームズ・ニューマンが1958年に著書『ゲーデルの証明』で発表したゲーデルの方式を少し修正したものは、基本的な公理のセットを表現するための語彙となる12の基本的な記号から始まります。 例えば、「何かが存在する」ということは∃という記号で表現できますし、「足し算」は＋で表現できます。

これらの12個の記号には、1から12までのゲーデル数が割り当てられています。

です。

。

d

です。

定数記号	ゲーデル数	Usual Meaning
~	1	not
∨	2	or
⊃	3	if…then…
∃	4	three があります…
=	5	等
0	6	zero
s	7	の後継者
(	8	句読点
)	9	パンクチュエーションマーク
,	10	パンクチュエーションマーク
+	11	plus
×	12	回

次です。 x、y、zから始まる変数を表す文字は、12以上の素数（つまり、13、17、19、…）にマッピングされます。

そして、これらの記号と変数の任意の組み合わせ、つまり構築可能な算術式や式の並びには、それぞれのゲーデル数が与えられます。

例えば、0 = 0を考えてみましょう。 この式の3つの記号は、ゲーデル数6、5、6に対応します。 ゲーデルは、この3つの数字の列を1つのユニークな数字、つまり他の記号の列では生成できない数字に変える必要があります。 これを実現するために、彼は最初の3つの素数（2、3、5）を取り出し、それぞれを記号列の同じ位置にある記号のゲーデル数まで上げ、それらを掛け合わせます。

このマッピングがうまくいくのは、2つの式が同じゲーデル数になることがないからです。 ゲーデル数は整数であり、整数は1つの方法でしか素因数分解できません。 つまり、2億4300万の素因数分解は、26×35×56であり、ゲーデル数を解読する方法は、0＝0という式しかありません。

ゲーデルは、さらにもう一歩踏み込みました。 数学的な証明は、一連の公式で構成されています。 そこでゲーデルは、すべての数式の列に、一意のゲーデル番号も与えました。 ここでは、2、3、5…という素数のリストから始めます。 そして、それぞれの素数を、列の同じ位置にある式のゲーデル番号まで上げ（例えば、0＝0が最初に来た場合は、2243,000,000×…）、すべてを掛け合わせます。

メタ数学の算術化

本当の利点は、メタ数学的記述と呼ばれる算術式に関する記述でさえ、それ自身がゲーデル番号を持つ式に変換できることです。

まず、”ゼロはゼロにならない “という意味の式 ~(0 = 0) を考えます。 この式は明らかに間違っています。

まず、「ゼロはゼロにならない」という意味の式 ~(0 = 0) を考えてみましょう。この式は明らかに偽ですが、2 の 1 乗 (記号 ~ のゲーデル数) に 3 の 8 乗 (開括弧記号のゲーデル数) をかけて、2¹ × 38 × 56 × 75 × 116 × 139 となります。

偽の公式であっても、すべての公式に対してゲーデル数を生成することができるので、これらの公式については、そのゲーデル数について話すことで、感覚的に話すことができます。

「式 ~(0 = 0) の最初の記号はチルダである」という文を考えてみましょう。

「式 ~(0 = 0) の最初の記号はチルダである」という文を考えてみましょう。この ~(0 = 0) に関するメタ数学的なステートメント (真) は、この式のゲーデル数に関するステートメントに変換されます。 もし ~(0 = 0) がチルダ以外の記号で始まっていたら、そのゲーデル数は少なくとも 2 の因子を持つことになります。

最後の文は、初歩的な記号を使って書き下すことのできる正確な算術式*に変換することができます。

この例を Nagel と Newman は、「ゲーデルの発見の核心にある、非常に一般的で深い洞察を例示している」と書いています。つまり、長い記号の連鎖のタイポグラフィ特性は、代わりに大きな整数の素因数分解の特性を語ることで、間接的ではあるが完全に正確な方法で語ることができるのです。”

「ゲーデル数 x を持つ式の列が存在し、それがゲーデル数 k を持つ式を証明する」というメタ数学的な記述、つまり「ゲーデル数 k を持つ式は証明できる」という記述についても、記号への変換が可能です。

G 自体

ゲーデルの特別な洞察力は、公式自身のゲーデル数を公式に置き換えることができるということでしたが、これはトラブルの種にしかなりませんでした。

置換がどのように働くかを見るために、(∃x)(x = sy)という公式を考えてみましょう。

ここで、記号yの代わりにmを式に導入してみましょう。これにより、(∃x)(x = sm)という新しい式が形成されます。 この式のゲーデル数は何と呼べばよいのでしょうか？ 伝えるべき情報は3つあります。 まず、ゲーデル番号 m を持つ式で、m を記号 y に置き換えました。そして、先に紹介した写像法により、記号 y はゲーデル番号 17 を持ちます。

置換は、ゲーデルの証明の核心をなすものです。

彼は、”The formula with Gödel number sub(y, y, 17) cannot be proved. “というようなメタ数学的なステートメントを考えました。 先ほど学んだ記法を思い出してみると、ゲーデル数sub(y, y, 17)を持つ式とは、ゲーデル数y(ある未知の変数)を持つ式を取り、この変数yを、ゲーデル数が17である記号があるところならどこでも(つまりyがあるところならどこでも)代入して得られる式のことです。

物事はトリッピーになってきていますが、それでも、私たちのメタ数学的なステートメントである「ゲーデル数 sub(y, y, 17) を持つ式は証明できない」は、一意のゲーデル数を持つ式に必ず変換されます。

さて、最後の代入です。 ゲーデルは、前の式の中で y があるところに n という数字を代入して、新しい式を作ります。 この新しい式は、「ゲーデル数sub(n, n, 17)の式は証明できない」というものです。

当然のことながら、G にはゲーデル数があります。 その値は何でしょうか？ 何と、sub(n, n, 17)でなければなりません。 定義によれば、sub(n, n, 17)は、ゲーデル番号nの式を取り、ゲーデル番号17の記号があるところならどこでもnを代入した結果得られる式のゲーデル番号です。 そして、Gはまさにこの公式です。

G はそれ自体、証明できないと主張しています。

では、G は証明できるのでしょうか。 もしそうであれば、ゲーデル数 sub(n, n, 17) の式を証明する式の列があるということになります。 しかし、それはGの反対で、そのような証明は存在しないということになります。 Gと～Gという反対の文は、一貫した公理系では両方とも真になることはありません。

しかし、Gは決定不可能ではあるが、明らかに真である。 G は「ゲーデル数 sub(n, n, 17) の式は証明できない」と言っていますが、まさにその通りです。

あなたは、何か追加の公理を仮定して、それを使ってGを証明すれば、パラドックスを解決できると思うかもしれません。 しかし、それはできません。 ゲーデルは、増強された公理系では証明できない新しい真の公式Gʹを（以前と同様の設計図に従って）構築できることを示しました。

一貫性の証明ができない

公理系が一貫していれば、それは不完全であるということを学んできました。 これがゲーデルの第一不完全性定理です。

公理のセットが決して矛盾を生まないことを証明できるとしたら、それはどのような意味でしょうか。 それは、「この公理の集合は一貫している」ということをメタ的に意味する公式を証明する、これらの公理から構築された一連の公式が存在することを意味します。

しかし、「公理のセットが不完全である」ということは、「証明できない真の公式がある」と言っているのと同じです。 この文は、私たちの公式 G に相当します。

だから、ゲーデルは矛盾による証明を作ったのです。 公理の集合がそれ自身の一貫性を証明できるなら、G を証明することができるでしょう。

ゲーデルの証明により、一貫性のある完全な数学体系の探求は終わりました。

ゲーデルの証明により、一貫性のある完全な数学体系の探求は終わりました。不完全性の意味は「完全には理解されていない」と、1958年にネーゲルとニューマンは書きました。

*興味のある方は、この文章を読んでみてください。 “x に 2 を掛けたものが 2¹ × 38 × 56 × 75 × 116 × 139 になるような整数 x が存在し、x に 4 を掛けたものが 2¹ × 38 × 56 × 75 × 116 × 139 になるような整数 x は存在しない。” です。 これに対応する式は次のようになります。

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

ここで sss … sss0 は後継記号 s の 2¹ × 38 × 56 × 75 × 116 × 139 コピーを表します。 記号・は「と」を意味し、基本語彙の中の長い表現の省略形です。

この記事はWired.comに転載されました。