Gödel 数

Gödel number

Göedel数に関する解説で、手元にある学生の頃に読んだものから引用しまとめようとしている初日に気になったことがあった。寺坂英孝編の『現代数学小事典』の序文で

「第1章「数学基礎論」などというと大変むずかしいものと思いがちだが、論理、集合論、自然数論と細別されているどれもが面白い実例がたくさん入れてあって、軽い読み物の感じもある。それでいて現代数学の尖端にせまるような、ゲーデルの不完全性定理の証明まで平易に説明されている。」

と書かれていたのを再読した。しかし「ゲーデルの不完全性定理」の項目を読み通してみた。そこでゲーデルの気持を理解しながら読もうとすると、学生の頃「説明のしかたは平易ではない！！」ことにすぐ気がついた。いま再読しても、これはゲーデルではなく、不完全性定理についてなんとなくわかる程度にわかるに過ぎないのじゃないか、と。いや、表現が難しいが。

このページを書きはじめてすぐに、「帰納的」「原始」「関数」とか数学的な形式化について述べる必要性にせまられた。二日目の感想を述べると、形式化については「味もおもしろみもないもの」とされてしまいがち。だが、実は形式的に記述された数学理論には、それ以前に直感的あるいは具体的内容をともなった理解が存在していたことを知らなければならない。舌でなめて味わってみないとその正体が判らない。

岩波数学入門辞典の解説

有限個または可算無限個の記号からなる数学の体系では、その体系で定式化されるすべての命題に対して、自然数を1つずつ重複しないように対応させることができる。このとき、命題に対応させた自然数をその命題のゲーデル数と呼ぶ。アルファベットと $\rightarrow , \mapsto , \\( , \$ \) だけを記号とする体系で、$ \rightarrow$ に$ 0 $ 、$ \mapsto $ に$ 1 $、$ \\( $に$ 2 $、$ \$ \)に$ 3 $、$ a $ に$ 4 $、$ b $ に$ 5 $、$ c $ に$ 6 $を対応させる場合を考える。この場合、例えば、命題 $$ \$a \rightarrow b\$ \mapsto \$c \rightarrow a \$ \rightarrow \$ c \rightarrow b \$$$ は、まず記号を読み換えて有限数列 $ 2,4,0,5,3,1,2,6,0,4,3,0,2,6,0,5,3 $にする。次に素因数分解を逆利用し、自然数 $ 2^2 3^4 5^0 7^5 11^3 13^1 17^2 19^6 23^0 29^4 31^3 37^0 41^2 43^6 47^0 53^5 59^3 $を対応させることができる。注1

前原昭二『数学基礎論入門(p.119)』の解説

形式化された証明とは、記号の有限列の有限列である。
ある規則にしたがって、「記号」、「記号の有限列」、「記号の有限列の有限列」に自然数を1つずつ対応させる。そのようにして対応させられた自然数をゲーデル数(Gödel number)とよぶ。

Gödelの不完全性定理

Incompleteness thorem

岩波数学入門辞典

この辞典にはゲーデルについて次の3つの項目がある。ただし「ゲーデルの」という修飾はなく「不完全性定理」である。これは数学基礎論の最も重要な定理でありゲーデルによって発見されたことを示している。

ゲーデル

Gödel, Kurt
1906-78 チェコスロバキアのブルノに生まれ、ウィーン大学で数学と物理学を学んだ。1931年「自然数論や集合論などの公理体系が無矛盾であれば、その体系のなかでは正しいとも間違いであるとも証明することのできない命題があることを主張する不完全性定理」を示し、数学界に衝撃を与えた。

ゲーデル数

"Make it as simple as possible, but not simpler."

Albert Einstein

不完全性定理

第１不完全性定理

第１不完全性定理は、「どんな公理系をとっても、(その公理系が自然数論の体系を含んでいれば)その公理系で定式化できる命題で、その公理系では証明することもできないし、その否定も証明できない命題が存在する」という定理である。

第１不完全性定理は「この命題は証明できない」という命題をゲーデル数を用いて自然数論の命題に翻訳することによって証明された。

第２不完全性定理

「どの公理系も、その中で自分自身の無矛盾性を証明できない」という定理。

寺坂英孝編『現代数学小事典(p.116)』ゲーデルの理論の骨子

二つの項変数$ x, y$ を自由変数として含む次のような数論的命題を考える。

$ G(x,y)$ : 「$ x$ はただ一つの自由変数を持つ述語（これを $ P_x - \\(t\$\)で表す）のゲーデル数であり、$ y $ は閉述語$ P_x \\( x\$\)の証明となっている命題列のゲーデル数である」

この命題はけっして漠然とした主張ではない。
ゲーデルの長い証明の大部分はこの命題が数論の形式的述語でキチンと記述できることを示すのに費やされている。

そして驚くべきことにこの命題は（真偽値$1,0 $をとる関数として）原始帰納的である。

$ x,y $ に数値が与えられたとき、それが何か数論の汎言語要素になっているか（否ならば $ G\\(x,y\$ \) は疑）、ともに何かのゲーデル数ならばもとの汎言語要素はそれから復元できるから、それらが命題の主張をみたしているかどうか、虱つぶしに調べてゆけば命題の真偽の判定はつく。

このように命題の真偽を判定する虱つぶしの方法がある場合、その命題はまずたいがい原始帰納的である。

さてこれから次の命題を作る。 $$ R(t)= \neg ( \exists y) G(t,y) $$

これは「もし $ t $ がただ一つの自由変数を持つ述語 $ P_t (z) $ のゲーデル数であれば、いかなる数 $ y $ も閉述語 $ P_t (t) $ の証明のゲーデル数とはならない。すなわち $ P_t (t) $ は証明不能である」という主張である。

さてこの $ R(t) $ 自身は変数 $ t $ のみを自由変数とする命題であり、なんらかのゲーデル数 $ q $ を持つ。

すなわち $ R(t)=P_{q}(t) $

この特定の定数である$ q $を$ t $に代入して得られる閉述語

$ R(q) = \neg ( $