ゲーデルの定理-3.2- 第１不完全性定理の証明(ゲーデル数で橋渡し)

前回からの続きでゲーデル数の話から始めます。

　形式的体系の言語Ｌは、可算無限個の記号と、有限個の記号を並べた記号列(論理式は全て記号列)と、記号列の有限列(証明の系列が含まれる)とから成りますが、これらにゲーデル数という自然数を一意的に割り当てます。以下簡単のために、記号の並びを式、式の並びを式列と呼ぶことにします。

　すると、記号と式と式列の集合では、式Ａの証明が式列Ｂである、といった関係が存在します。そしてゲーデル数の集合では、式列の集合での関係と真偽が一致するような関係が構築できることがゲーデルにより示されました。ここでゲーデル数の集合での関係というのは、普通に自然数の間での関係として考えられるものです。つまりここで我々は１つの形式的体系に加えて、モデルとなりうる集合２つを考えました。１つ目は記号と式と式列とを元として、それらの間に様々な関係のある集合Γです。これはいわば論理式の世界です。２つ目は自然数の集合Ｎで、その元である自然数の間にも様々な関係が考えられます。これは自然数の世界です。そして１つの形式的体系とは、自然数の間の関係を論理式で表現できるようにした体系(より正確には構造)です。そしてこの体系で使われる論理式や式列は、それ自体が集合Γの元です。

　そして重要な点ですが、ゲーデルの証明のようなメタ数学的証明に際して、ΓやＮにおけるいくつかの真理をフル活用します。そのいくつかは有限の手続きで、いわば手作業で確認できる真理ですが、素因数分解の一意性のように整数論で証明される命題も含まれます。

　ここで自然数の集合Ｎでの関数や関係とそれらを示す論理式とを区別するために、後者は太字で記すことにします。そして後者は集合Γの元になります。
　　１;自然数の１自体　　　　　　１;１を示す記号
　　ａ;特定の自然数ａ自体　　　　ａ;ａを一意的に示す対象式。以後は定数項と呼ぶ。
　　ｘ;自然数を範囲とする変数ｘ自体　ｘ;変数ｘを示す記号
　　Ｐ(ｘ,ｙ);変数ｘ,ｙの２項関係　　　　　Ｐ(ｘ,ｙ);関係Ｐ(ｘ,ｙ)を示す論理式(述語式)
　　Ｐ(ａ,ｂ);自然数ａ,ｂが関係Ｐにある　Ｐ(ａ,ｂ);関係Ｐ(ａ,ｂ)を示す論理式(述語式)

　ここで「ａを一意的に示す対象式」とした意図を説明します。各自然数にひとつずつ定数記号を割り当ててあれば「ａを示す定数記号」とすれば良いのですが、定数記号０,１,２・・・に替えてｓ(((０)))のような関数式(対象式)を使う方式も使えますし、この方式がむしろ普通です。かといって「ａを示す対象式」というのは一つに限りません。そこで、その体系で各自然数に１：１対応させるように決められた対象式を「ａを一意的に示す対象式」としました。しかしこれでは長いので、以後は簡単に定数項と呼ぶことにします。
　なお念のために述べれば、Ｐ(ｘ,ｙ)は自由文でＰ(ａ,ｂ)は確定文です。

　さてある記号・式・式列をＡとしたとき、そのゲーデル数を~Ａ~で表すことにします。
記号3.2-1. ~Ａ~　；記号・式・式列であるＡのゲーデル数。

　実はRef-3では、"「"を左右反転したような記号と"「"とを使っているのですが、シフトJISにないので"~"を使うことにします。ゲーデル数なのでＧ(Ａ)のような記号を使いそうなところですが、そうしなかったのが読者の理解を助けるための著者の前原氏の工夫です。不完全性定理の証明で扱いたい関数の多くは自然数から自然数への関数であり、対応する論理式が形式的体系に存在します。ところがゲーデル数は式列等から自然数への関数であり、「Ａ」を記述する対象式というものは、今想定している形式的体系の中では定義できません。Ｇ(Ａ)などと表記するとこの事実をうっかり忘れて、関数Ｇ(Ａ)を示す論理式などというものが存在すると勘違いするかも知れません。

　つまり「式Ａのゲーデル数はａである。；ａ＝~Ａ~」という関係をそのまま記述する論理式は存在しません。しかし例えば「式ｘ＝１のゲーデル数はａである。；ａ＝~ｘ＝１~」という式と自然数との関係を記述する論理式は存在しませんが、「ａは、ｂ1をゲーデル数とする記号ｘとｂ2をゲーデル数とする記号＝とｂ3をゲーデル数とする記号１とをつないだ式ｘ＝１のゲーデル数である」つまり「ａ＝~ｘ＝１~かつｂ1＝~ｘ~かつｂ2＝~＝~かつｂ3＝~１~」という関係なら、自然数ａ,ｂ1,ｂ2,ｂ3,の間の関係ですから、これを記述する論理式は存在します。具体的にはとても複雑なものになりそうですが。

　すなわち、記号・式・式列の集合Γでの命題、自然数の集合Ｎでの命題、それを記述する論理式の間に対応関係が成り立っています。
　　Γでの命題　；式Ａは記号Ｂ1,Ｂ2,・・・,Ｂnをこの順に並べたものである。
　　Ｎでの命題　；n+1個の自然数~Ａ~,~Ｂ1~,~Ｂ2~,・・・,~Ｂn~の間の関係
　　論理式　；Ｎでの上記命題を記述する論理式

　こうしてゲーデル数を定義できれば前回の記事の似非述語式(^_^)Ｂew(Ａ)は次のようにまともな論理式にできます。

記号3.2-2. Ｂew(ａ)　ただし、ａ＝~Ａ~

　ａは自然数ａを記述する定数項であり、先に説明した通り、自然数ａと1:1対応する対象式です。例えば自然数３に対応する対象式には定数項３の他に１＋２,７－４といった関数式もありますが、自然数３の定数項は３だけです。後に自然数ｎを記述する定数項ｎのゲーデル数を返す関数Ｚ(ｎ)というものが登場しますが、関数Ｚ(ｎ)の値がただひとつに決まるのは、自然数ｎを記述する定数項ｎをただひとつの対象式に決めてあるためです。

　では続きは次回としましょう。