ゲーデルの定理 -証明とゲーム-

　ゲーデルの第一不完全性定理の証明は具体的に肯定も否定も証明できない閉論理式を構成すことで行われましたが、ここで次のような疑問が生じます。
　・肯定も否定も証明できない閉論理式はここで構成されたもの以外にもあるのか？
　・あるとすればどんなものなのか？

　いまだ未解決の数学的問題のどれかが実は肯定も否定も証明できない問題かもしれません。が、ここでちょっと前提が・・。証明可能性は公理系によりますから、ここではほとんどの数学的問題は展開できるとされている集合論のＺＦ公理系で考えてみるのが妥当というものでしょう。例えばペアノ公理系ではグッドスタイン数列の問題[*1]やヘラクレスとヒドラの問題[*2]などは証明できないことがわかっていますが、これは整列集合が導入されたＺＦ公理系では証明できます。また連続体仮説はＺＦ公理系では証明できないので、それを公理として加えたＺＦＣ公理系が使われたりします。

　このような公理は成立するのが自然なように見えますが、第一不完全性定理の証明で出てきたＵには少し人工的なところがあります[*3]。Ｕは自然数モデルでの命題を記述した論理式になりますが、その具体的な形が採用する言語やゲーデル数の決め方により異なります。つまりゴールドスタン数列の問題のような本来の自然数世界の命題というよりは、自然数世界とは別の論理式世界の命題を暗号化して自然数世界の命題として人工的に作り上げた命題と言えます。似た例として例えば、将棋やチェス、囲碁などのゲームの必勝法問題を考えてみましょう。ゲームのある局面が先手必勝か後手必勝か引き分けか、という命題が証明可能かどうかです。この命題を自然数世界の命題として記述することは可能です。ゲームの局面に適当に自然数を当てはめれば、ルールやゲームの推移、決着判定などは自然数世界の命題になります。

　このようなゲームの問題は何らかの数学的法則があって証明ができるというよりは、最終的には枚挙法で可能な手順をしらみつぶしに調べるしか方法がない可能性がおおいにあります。すると可能な手順数が無限であれば、原理的に証明できないと考えられるでしょう。つまり、ゲーム世界の命題を自然数世界の命題として暗号化したものは、肯定も否定も証明できない可能性があります。

　実際、論理式世界とゲーム世界には次のような対応が考えられます。
　　　閉論理式(真偽の定まった命題)　　ゲームの一局面
　　　証明できる　　　先手必勝である
　　　否定が証明できる　　後手必勝または引き分け
　　　証明できない　　　終わらない手順がある

　このように見てみるのも不完全性定理の理解のための有効なイメージかも知れません。


－－－－－－－－－－－－－－－－－－－－
*1) ウィキペディアの記事
*2) 照井一成（京都大学数理解析研究所）(2015/04/24)
　　田中一之他『ゲーデルと20世紀の論理学(第3巻)不完全性定理と算術の体系』東京大学出版会(2007/03) p27「付録１.ヘラクレスとヒドラの戦い」

*3) ここは感覚的なことなので少し補足。
　グッドスタイン数列やヘラクレスとヒドラの問題については小さな数の範囲でなら実作業で確認できるし、一般には実作業での確認にはとてつもなく時間(というより手数)がかかるにしても、正しいと認めることはできます。これは、集合論における無限に続く枝分かれした半順序系列が、ペアノ自然数における無限に続く１本の順序系列と同じくらい、我々には自然に見えるということを意味します。
　連続体仮説については成立するのと成立しないのとどちらが自然に見えるかは人によって違いそうです。自然数濃度と実数濃度との中間濃度を持つ謎の集合!!、があった方が楽しそうじゃないか。ただどうもこの謎の集合はあまり豊かな性質を見せてくれないようです。この件については、さみだれハーフムーンの数学コラムのコーエンの強制法と連続体仮説の否定モデル 第11/11章におもしろい見解が述べられています。豊かな性質を見せてくれないのではなくて、人間の能力では(今のところは)見えないだけなのかも知れません。