ゲーデルの証明の仕組み

ホーム ゲーデルの証明の仕組み コメント 保存 記事 後で読む シェア Facebook コピー済み！リンクをコピー Eメール ポケット Reddit Ycombinator コメント コメント 保存 記事 後で読む 後で読む 解説 ゲーデルの証明の仕組み Natalie Wolchover 著 2020年7月14日 彼の不完全性定理は、数学における「すべてを網羅する理論」の探求を破壊しました。約1世紀後、私たちはその結果にまだ対処しています。 コメント 保存 記事 後で読む どんな数学的システムにも、決して証明できない命題が存在します。Olena Shmahalo/Quanta Magazine はじめに 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^6 × 3^5 × 5^6、つまり243,000,000になります。このマッピングは、2つの公式が決して同じゲーデル数を持つことがないため機能します。ゲーデル数は整数であり、整数は一意にしか素因数分解できません。したがって、243,000,000の素因数分解は2^6 × 3^5 × 5^6しかなく、ゲーデル数をデコードする唯一の方法は、公式0 = 0しかないということです。 ゲーデルはさらに一歩進みました。数学的証明は公式のシーケンスで構成されます。そのため、ゲーデルは公式のシーケンスそれぞれにも一意のゲーデル数を与えました。この場合、彼は以前と同じように素数のリスト（2、3、5など）から始めます。次に、各素数をシーケンス内の同じ位置にある公式のゲーデル数で累乗し（例えば、0 = 0が最初に来る場合、2^243,000,000 × …）、それらをすべて掛け合わせます。 メタ数学の算術化 真の利点は、公式に関する命題、メタ数学的命題でさえ、それ自体が独自のゲーデル数を持つ公式に翻訳できることです。まず、公式~(0 = 0)、「ゼロはゼロに等しくない」を考えてみましょう。この公式は明らかに偽です。それにもかかわらず、それはゲーデル数を持っています。それは、2を1（チルダ記号のゲーデル数）のべき乗、3を8（開き括弧記号のゲーデル数）のべき乗などで掛け合わせたもので、2^1 × 3^8 × 5^6 × 7^5 × 11^6 × 13^9となります。すべての公式、偽の公式でさえゲーデル数を生成できるため、それらのゲーデル数について語ることで、これらの公式について合理的に話すことができます。例えば、「公式~(0 = 0)の最初の記号はチルダである」という命題を考えてみましょう。この（真の）メタ数学的命題は、公式のゲーデル数に関する命題に翻訳されます。つまり、その最初の指数がチルダのゲーデル数である1であるということです。言い換えれば、私たちの命題は、2^1 × 3^8 × 5^6 × 7^5 × 11^6 × 13^9が2の単一の因数しか持たないことを意味します。もし~(0 = 0)がチルダ以外の記号で始まっていたら、そのゲーデル数は少なくとも2つの2の因数を持つことになります。したがって、より正確には、2は2^1 × 3^8 × 5^6 × 7^5 × 11^6 × 13^9の因数ですが、2^2は因数ではありません。私たちは最後の文を、基本的な記号を使って書き留めることができる正確な算術的公式に変換できます。この公式はもちろんゲーデル数を持ち、素数のべき乗に記号をマッピングすることで計算できます。ネイゲルとニューマンは、この例は「ゲーデルの発見の中心にある非常に一般的で深い洞察を例示しています。長い記号の連なりのタイプライター的な特性は、代わりに大きな整数の素因数分解の特性について語ることによって、間接的ではあるが完全に正確な方法で語ることができます。」と述べています。 「ある公式のシーケンスで、ゲーデル数kを持つ公式を証明するシーケンスが存在する」というメタ数学的命題、つまり「ゲーデル数kを持つ公式が証明できる」という命題も、記号への変換が可能です。この種の命題を「算術化」する能力が、この偉業の舞台を整えました。 G 自身 ゲーデルのさらなる洞察は、公式自身のゲーデル数をその公式自体に代入できることでした。これが多くの問題を引き起こしました。代入がどのように機能するかを見るために、公式(∃x)(x = sy)を考えてみましょう。（これは「yの後続である変数xが存在する」、つまり「yには後続がある」と読めます。）すべての公式と同様に、それはゲーデル数、つまり大きな整数mを持ちます。ここで、このmを公式の記号yの代わりに導入します。これにより、新しい公式(∃x)(x = sm)が形成されます。これは「mには後続がある」という意味です。この公式のゲーデル数を何と呼ぶべきでしょうか？伝えるべき情報は3つあります。私たちはゲーデル数mを持つ公式から始めました。その中で、私たちは記号yの代わりにmを代入しました。そして、前に導入したマッピングスキームによると、記号yはゲーデル数17を持ちます。したがって、新しい公式のゲーデル数をsub(m, m, 17)と指定しましょう。代入はゲーデルの証明の核心を形成します。彼は、「～の」といったメタ数学的命題を考慮しました。