ゲーデルの定理-3.3- 第１不完全性定理の証明(ゲーデル数の実際)

前回からの続き

　今回はゲーデル数の求め方の一例を具体的に示しましょう。参考にしたのは前原のRef-3です。でもあまり具体的な数値を求めようとはしない方が無難です。巨大すぎて頭が爆発します(^_^)。それよりも、素数をうまく使っているなあということが何となくわかって、なるぼど確かに一意的に対応しているらしいとわかれば、門外漢が理解するにはそれで充分でしょう。さて具体的には使う記号や当てはめ方で任意性が出てきますが、次のような要領になります。

定義3.4-1
　論理記号として以下のものだけを使い、そのゲーデル数には次の奇数を当てはめます。
　　　（　左括弧　　１
　　　）　右括弧　　３
　　　→　ならば　　５
　　　￢　否定記号　７
　　　∧　かつ　　　９
　　　∨　または　　11
　　　∀　全ての　　13
　　　∃　存在する　15
　　　＝　等号　　　19
　可算無限個の定数記号には23以上の素数を当てはめます。
　　　23,29,31,・・・
　可算無限個の変数記号には23以上の素数の２乗を当てはめます。
　　　23²,29²,31²,・・・
　可算無限個の関数記号には23以上の素数の３乗を当てはめます。
　　　23³,29³,31³,・・・

　ここで、"＝","∃","∧","∨"などを使わず他の論理記号で表記する道もあります。また自然数をモデルとする体系だけ考えるなら、定数記号として"０"だけを、関数記号として「～の後者」を示す"ｓ"だけを使い、可算無限個の定数記号や関数記号は使わない道もあります。論理記号の数が９個から減ったとしても大勢に影響はないでしょうが、可算無限個の記号が変数記号だけになるとかなり複雑さが減る印象を受けます。またRef-3では変数記号に１階のみならず2階,3階,・・・のものも使い、ｎ階変数には素数のｎ乗を当てはめています。要は、どのような道を取るにせよ、可算無限個の記号が可算無限種類あったとしても素数のｎ乗を当てはめて対処できるということです^*1。

　また多くの本では、述語論理の話では命題変数記号は使っていません。命題論理の公理は命題変数記号で書かれているのですが、述語論理体系ではそれが例えば、「命題変数に全ての閉論理式を代入した式」と言ったように定義されます。つまり公理の数が可算無限個になりますが、それでメタな論証がうまくいくのかどうかは一見では納得しずらいかも知れません。一応説明すれば、証明列の中で公理として使うのはあくまでも有限個の論理式であり、それらが公理だということが有限のステップで判定できれば、それで証明に使えるのだ、ということです。

定義3.4-2
　さて使う記号のゲーデル数がすべて定義できたので、記号列のゲーデル数は次のように定義します。
　　　ｎ個の記号から成る記号列Ｘ₁Ｘ₂Ｘ₃・・・Ｘ_i・・・Ｘ_nのゲーデル数は、
　　　　2^g1*3^g2*5^g3*・・・*p_i^gi*・・・*p_n^gn
　　　ただし、
　　　　　giは、記号Ｘ_iのゲーデル数
　　　　　p_iは、ｉ番目の素数
　つまり、記号列の先頭からｉ番目の記号に、２から数えてｉ番目の素数を該当記号のゲーデル数で累乗した数を当て、こうして得た数を全記号について掛けた数が、この記号列のゲーデル数です。

　さらにこの定義で、記号を記号列に置き換え記号列を式列に置き換えれば、式列のゲーデル数が定義できます。

　以上のように可算無限個の記号を使っても十分にゲーデル数は構成できますが、記号を有限個だけ使う方法がスマリヤンの本[Ref-s3, p22]に出ています。これだと少し複雑さが減るでしょう。具体的には上記では可算無限個になった定数記号、変数記号、関数記号の替わりに次の記号を使います。ただし本当は「'」(アポストロフィー, apostrophe)ではなく「´」(プライム, prime」なのですが、JISコードでは使いにくいのでアポストロフィーを使います^*2。

　　定数記号; ０,０',０'',０''',・・・
　　変数記号; ｖ,ｖ',ｖ'',ｖ''',・・・
　　関数記号; ｆ,ｆ',ｆ'',ｆ''',・・・

　定数の記述では常法ですが、それを変数記号や関数記号にも適用するわけで、なるほどうまい方法です。変数記号や関数記号の場合は、実際にはそれぼど多くの種類は使わないでしょうしね。


　続く

－－－－－－－－－－－－－－－－
*1) ここは色々とあるが。
　例えば論理記号として"￢","→","∀",だけ使い他は省略形とする方式も多いが、人間にとっては省略形を瞬間的に理解するのは結構つらいものがある。つまりスムースには読めない。
　自然数以外のモデルでも対象となる集合の元が可算個であれば、全ての元に一意的な自然数を割り当てて自然数による構造Ｎの中に構築してしまえる場合もある。ゲーデル数とはまさに、これを論理式の集合に対して行ったものだ。

*2) 以下の記号はなかなか区別しずらい。
　シングルクォーテーション(single quotatiion); 単語を囲む時に使い、前方に使う記号と後方に使う記号の２種類ある。後方の閉じる記号は日本の標準キーボードの「７」の上の「’」。
　アポストロフィー(apostrophe); シングルクォーテーションと同一字体も使われる。
　プライム(prime); 上記２つとは明確に区別。UNIコードでないと表示しずらいようだ。スマリヤン[Ref-s3) p22]は明確にプライムと述べている。