ゲーデルの不完全性定理を直感的に理解する：数学の限界に挑んだ証明の全貌（2020年版）

数学や論理学の基礎を揺るがした、クルト・ゲーデルによる「不完全性定理」の証明。なぜこの証明が重要なのか、どのような論理構造で成り立っているのかを分かりやすく解説した、2020年公開の秀逸な解説記事です。

もしこれに興味があるなら、「ゲーデル、エッシャー、バッハ：あるいは不思議の環」を読むことを強くおすすめするよ。

数学全体の中でこれが一番好きな証明だ（これまでに触れたものの中でだけど）。試験中にゲーデル数を使って、ある命題が証明不可能であることを証明した時の感覚は、本当に現実離れしてたな。

しかし、Gは決定不能だが、明らかに真である。

それは…正直あまり正しくないね。よりによってQuantaでそれを見るのは驚きだ。

ゲーデルの（別の）完全性定理は、一階述語論理においては、あらゆる可能なシナリオで意味論的に真であるものは、統語論的に証明可能であると言っている。だから、もしGが「明らかに真」なら、それは証明可能であるはずだ。

これらの定理が互いに矛盾しないのは、一階述語論理においてGが真であるとは限らないからだよ。その真偽は、ゲーデルが構築した仕組みとは独立したものなんだ。

入門的なテキストではあまり深入りしなくてもいい部分かもしれないけど、実はこれを知っておくと結果全体が把握しやすくなるし、スコーレムのパラドックスのような、直感に反するさらに多くの結果へと繋がっていくよ。

素晴らしい解説だよ：https://stopa.io/post/269

動画が好きなら、読書の補助として以下を見るといい。

Joel David Hamkins - Oxford lectures on the philosophy of mathematics
"The Gödel incompleteness phenomenon"
https://www.youtube.com/watch?v=Y5trjR5aw0k

あとこれも。
"Gödel's incompleteness theorems: The proof that broke mathematics" | Joel David Hamkins
https://www.youtube.com/watch?v=Sza69An_H8o
タイトルは釣りっぽいけど、中級レベルの素晴らしいトークだよ。

追記：スペル修正

ゲーデルの不完全性定理は、数学における最も重要な結果だと考えてる。と同時に、この話題が出たときは、人間中心主義や宗教といった周りを取り巻く胡散臭い議論を払拭するために、よくこのエッセイを紹介しているよ：

https://shs.cairn.info/revue-internationale-de-philosophie-2005-4-page-513?lang=en

自分が理解できるほど頭が良くないだけなのかもしれないけど、『ゲーデル、エッシャー、バッハ』をなんとか読み通してみても、結局その証明はこじつけのように思えるんだ。自己言及に依存しすぎているというか。

停止性問題の決定不能性からも不完全性を導くことができるよ。（例えば）ペアノ算術におけるすべての命題が証明可能だと仮定すれば、停止性問題を解決できてしまうことに注目してみて。チューリングマシンの実行の停止をゲーデル数を使って整数としてエンコードし、その実行が停止するという命題を書くんだ。その命題か、その否定のどちらかが証明可能になるはずだから、両方の証明を同時に探せばいい。

関連する定理として、ロジャースの再帰定理がある。これはプログラムを実行したときに自身のソースコードを出力するようなものが作れるという定理で、（これを使えばどんなチューリング完全なプログラミング言語でも実装可能だよ。）

Show HN: 最近、不完全性定理について、特にソフトウェアの言語で表現した内容のトークをしたんだ。まずは歴史的背景と、彼が研究を行った哲学的文脈の議論から始めている。トークの後半は、ゲーデルのアイデアの核心にある美しい本質を、技術的な知識を持つ一般層向けに伝える試みだよ。これはトークのスライドで、ウェブページ化はしていないから人によって合う合わないはあるかもね。
リンク: https://www.gregfjohnson.com/godel_incompleteness/

これについて共有される記事やリンクが、どれもこれも核心に触れる前に過去の話を長々と紹介するのには正直イライラするね。

2+2=4という事実にしても、人類が数値表現を求めて歴史の中でどういう数体系を編み出したか、なんていう7段落もの前置きを語ってから、ようやく実際の事実や詳細に軽く触れるだけ、みたいな。