ゲーデルの定理-3.1- 不完全性定理の証明(アイディア)

前回からの続き

　不完全性定理の証明に入る前に用語を整理しておきましょう。

　・記号列とは、有限個の記号の１次元配列。記号１個の記号列もある。
　・論理式とは、決められた文法に沿った記号列。
　・対象式(対象項)とは、モデルの特定の元または不特定の元を記述する論理式。
　　　特定の元を記述する式は定数項、不特定の元を記述する式は変数項
　・述語(述語式)とは、モデルでの命題を記述する論理式。真偽を持ちうる。
　・閉論理式とは、自由変数を持たない(変数があれば束縛変数である)論理式。モデルが決まれば真理値はただ一つに定まる。

　ここでモデルを固定したとき、述語式の真偽はそのモデルの真偽で定義します。モデルの真偽は、観測や有限手続きでの決定は困難か不可能だとしても、定まってはいるものとみなします。そして論理式の世界で公理を定めれば、証明が可能になります。ただしＡが自由変数ｘを含んでいれば真偽は元により異なり不定となります。変数がすべて∀や∃で束縛された閉論理式なら真偽は確定します。この区別は大切なので今後は本記事独自の言葉として、真偽が不確定な論理式を「自由文」、確定するはずの論理式を「確定文」と呼ぶことにします^*1。

　また、証明できる、証明できない、という論理式世界の命題をよく使いますので、記号を定めておきます。
　記号3.1-1a　|--- Ａ　;論理式Ａは証明できる
　記号3.1-1b　|-x- Ａ　;論理式Ａは証明できない

　ここで「表す」とか「示す」ではなく「記述する」という言葉を使ったのは「表現する(represente)」という言葉が証明可能性、つまり公理系を設定して初めて定義できる性質と関連した定義をされているからです。すなわち、「あるモデルにおける命題Ａが述語式Ａで表現される(表現可能)」というのは、次の２つとも成り立つことと定義されています[Ref3)p101-102, Ref7)p219, Ref-s3)p150]^*2。

　命題3.1-1a Ａが成り立つならば(真ならば)、　|--- Ａ　(Ａは証明可能)
　命題3.1-1b Ａが不成立ならば(偽ならば)、　　|--- ￢Ａ　(￢Ａは証明可能)

　ここでＡが自由変数ｘを含んでいれば真偽が不確定な自由文となりますが、その場合も、ｘに特定の元ｔを代入したときにモデルのどの元についても上記２つが成り立つならば、「命題Ａ(ｘ)が述語式Ａ(ｘ)で表現される(表現可能)」と定義します。ｘに代入する元が異なれば真偽は異なるかも知れませんが、真偽と証明可能性との対応はどの元でも成立しているということです。このような自由文についての表現可能性を特に「数値別に表現される」と呼ぶこともあります[Ref3)p101-102]。また関数式Ｆ(ｘ)と変数項ｙを使った述語式「ｙ＝Ｆ(ｘ)」が、関数と元との関係を数値別に表現しているとき、単に「この関数が関数式Ｆ(ｘ)により表現される」ともいいます[Ref4)p182, Ref7)p219]。関数式Ｆ(ｘ)と述語式Ｒ(ｙ)がそれぞれ関数Ｆ(ｘ)と関係Ｒ(ｙ)を数値別に表現しているときは、変数記号ｘに対象式ｔを代入したＲ(Ｆ(ｔ))は関係Ｒ(Ｆ(ｔ))を表現しています。

　後のために補足しておくと、命題Ａが述語式Ａで表現されるならば、命題3.1-1aの逆が成り立つことが比較的簡単に証明できます。
　命題3.1-1c |--- Ａ ならば、命題Ａが真

証明3.1-1
　1) Ａが偽ならば、　|--- ￢Ａ　　∵命題3.1-1b
　2) |--- ￢Ａ ならば、　|-X- Ａ　　∵無矛盾なら^*3
　3) Ａが偽ならば、　|-X- Ａ　　∵ 1),2)からの三段論法
　4) |--- Ａ ならば、命題Ａが真　　∵ 3)の対偶


　さてゲーデルによる不完全性定理の証明のアイディアは次のようなものですが、このままでは拙い点があります。それは何でしょうか？

第１段階
　まず、「述語式Ａは証明できる」という命題が述語式Ｂew(Ａ)ですべてのＡについて記述され、次のことが証明できたとします。もちろん、これはメタ数学的に証明すべきことです。
　命題3.1-2a　　|--- Ａ が真ならば、　|--- Ｂew(Ａ)
　命題3.1-2b　　|--- Ｂew(Ａ) ならば、　|--- Ａ

　命題3.1-2aは、そのように記述したいことであり、その逆である命題3.1-2bは公理系が論理式の集合というモデルについて健全ならば成り立つはずのことです。しかしこれは「|--- Ａ」という論理式世界の命題が述語式Ｂew(Ａ)で表現可能とは言っていません。実際、「|--- Ａ が真」の場合を１として、「|--- Ａ が偽」の場合には２つの場合がありえます。場合３はまさに統語論的に不完全な場合です。もちろん、残る第４の場合は・・・矛盾です。
　場合１　　|--- Ａ かつ、|-x- ￢Ａ
　場合２　　|-x- Ａ かつ、|--- ￢Ａ
　場合３　　|-x- Ａ かつ、|-x- ￢Ａ

　さて命題3.1-2a,bが成り立てば場合１が|--- Ｂew(Ａ)と同値であり、Ａに￢Ａを代入すれば、場合２が|--- ￢Ｂew(Ａ)と同値であるとわかります。つまり、場合１,２,３はそれぞれ以下の場合と同値になるわけです。
　場合１　　|--- Ｂew(Ａ) かつ、|-x- ￢Ｂew(Ａ)
　場合２　　|-x- Ｂew(Ａ) かつ、|--- ￢Ｂew(Ａ)
　場合３　　|-x- Ｂew(Ａ) かつ、|-x- ￢Ｂew(Ａ)

第２段階
　次に、以下の述語式が証明できるような述語式Ｕが存在したとします。もちろん、これは証明すべきことです。また公理系は当然あるものに固定されているとします。
　式3.1-1a　　Ｕ→￢Ｂew(Ｕ)
　式3.1-1b　　￢Ｂew(Ｕ)→Ｕ

　このとき、それぞれの対偶は証明できます。
　式3.1-2a　　Ｂew(Ｕ)→￢Ｕ
　式3.1-2b　　￢Ｕ→Ｂew(Ｕ)

　なお、→も←も成り立つという意味の論理記号⇔(同値と読む)を使えば、式3.1-1a,bや式3.1-2a,bは次のように略記できます。つまり以下は、２つの式を∧で結合した式の略記になります。
　式3.1-1　　Ｕ⇔￢Ｂew(Ｕ)
　式3.1-2　　￢Ｕ⇔Ｂew(Ｕ)

　圧倒的多数の論理式では式3.1-1a,bが記述する命題がそもそも真ではないでしょうが、証明できる式Ｕがひとつでも存在すれば、それで十分です。

証明3.1-2
　1) もし |--- Ｕ だとすれば、
　　1-1) 式3.1-1aより |--- Ｂew(Ｕ)
　　1-2) すると式3.1-2aより |--- ￢Ｕ
　　1-3) 矛盾である。
　2) もし |--- ￢Ｕ だとすれば、
　　2-1) 式3.1-2bより |--- Ｂew(Ｕ)
　　2-2) すると式3.1-1bより |--- Ｕ
　　2-3) 矛盾である。
　3) ゆえに公理系が無矛盾ならば、Ｕも￢Ｕも証明できない。
　4) すなわち、公理系が無矛盾ならば統語論的に不完全である。


　この証明の難点は、そもそも述語式Ｂew(Ａ)がおかしなものであることです。不完全性を議論しているのは「自然数の公理系」であり「記号列の公理系」ではありません。述語の対象項には自然数を記述する対象式しか使えません。しかるにＡは記号列である論理式を記述する対象式になっています。

　そこでゲーデルはＡのところに、記号列と1:1対応している自然数を代入するというアイディアを考えました。この記号列(および記号列の並びおよび記号そのもの)と1:1対応している自然数をゲーデル数と言います。ゲーデル数を使うことにより、論理式の世界の命題を自然数の世界の命題に置き換えて、その命題を記述する論理式を作ることができるようにしたのです。

続く

－－－－－－－－－－－－－
*1) 類書では、確定文は「閉論理式」とよび、自由文は「自由変数を持つ文」とよぶのが普通だが、確定文と自由文の方が対でわかりやすそうな気がする。また単に文(sentence)で確定文すなわち閉論理式を意味する用法もよく使われている[Ref5)p64, Ref-s3)p24]。
*2) Ref-s3ではスマリヤンは「定義する(define)」「完全表現する(completely represent)」という言葉を当てている。両者は別の定義をされるが、同値であることが証明されている。
　　[2015/11/22追記] Ref-3では「数値別に表現される(to be numeralwise expressed)」と記されていたが、Ref-s3では"express"は「言及する」と和訳される別の意味に使われていた。英語でも複数の表現があるようなので、スタンフォード大学の"Stanford Encyclopedia of Philosophy"の記事の一部から引用する。
[Warning: Here the terminology in the literature varies a lot: “strongly represent” is sometimes called, e.g., “represent”, “numeralwise express”, “bi-numerate”, “define” or “strongly define”; “weakly represent” is in turn also expressed, e.g., by “represent”, “define”, “weakly define”, or “numerate”. One should be careful here and focus on the relevant definitions, and not let the words mislead.]

*3) 今後も特に断らないが、考えている形式的体系は無矛盾と仮定している。矛盾した体系について考えても意義が少ないので。その形式的体系が実際に無矛盾か否かは、ゲーデルの第２不完全性定理によれば、その体系の中では証明できない。

－－－－－－－－－－－－－
References
1) 野崎昭弘『不完全性定理―数学的体系のあゆみ(ちくま学芸文庫)』筑摩書房(2006/05)
2) 日本数学会『岩波数学辞典-第3版』岩波書店(1985/12) [71.記号論理]の項
3) 前原昭二『数学基礎論入門』朝倉書店(1977)
4) 上江洲忠弘『述語論理・入門―基礎からプログラムの理論へ』遊星社(2007/04)
5) 田中一之他『ゲーデルと20世紀の論理学(第2巻)完全性定理とモデル理論』東京大学出版会(2006/10)
6) 田中一之他『ゲーデルと20世紀の論理学(第3巻)2不完全性定理と算術の体系』東京大学出版会(2007/03)
7) リヒャルト・デテキント(Dedekind, Richard);渕野昌(Fuchino, Sakae 訳)『数とは何か そして何であるべきか(ちくま学芸文庫)』筑摩書房(2013/07/10)

s3) Smullyan, R.M.(著);高橋昌一郎(訳)『ゲーデルの不完全性定理』丸善(1996/07/25)