5.ゲーデルの不完全性定理III

 いよいよ『ゲーデルは何を証明したか』の最終回です.本書の一番難しいところでもあります.とはいっても本格的にゲーデルの不完全性定理を証明するわけではないので,丁寧に読んでいけば必ず理解できます.でも,念には念を入れて,ちょっくらてこ入れしておきます.

《ゲーデルの不完全性定理をわかりやすく言い換えると》

a 自己言及命題が作れるほどの複雑性を具えた形式的体系では,次のような奇妙な命題を作ることができる
b 「この命題は証明できない」(命題G)
c 命題Gが証明されるなら,命題Gは偽である
d 命題Gが証明できないなら,命題Gは真である
e そして,命題Gが証明できないことが実際に証明されることになる
f これによって,この形式体系には,「真であるが証明できない命題が存在する」ことが証明されたことになる(体系の不完全性の証明)

《これまでに学んだ事柄で特に重要な点の復習》

・ゲーデルが行おうとしていることは体系の「無矛盾性」や「完全性」などに関する超数学的命題(数学の外部の立場)の絶対的証明(数学の内部の立場)である.
ラッセルの二律背反
  a 正規集合:自分自身を元として含まない集合
  b 非正規集合:正規集合ではない集合
  c 集合N:全ての正規集合の集合
  d Nが正規集合であると仮定
    =>Nは正規集合なのでNの元=>Nは自分自身を元として含むので非正規集合=>仮定に矛盾
  e Nが非正規集合(=自分自身を元として含む集合)であると仮定
    =>NはN自身の元=>Nは正規集合の集合なのでNは当然正規集合=>仮定に矛盾
・リシャールのパラドックス
  a 定義の整列(算術的性質に関する定義を整列させる規則を作る.定義の字数やアルファベット順などで)
       =>整列順に定義に自然数を1から順に割り当てる
  b リシャール数:上記の方法で割り当てられている数について,その数がその数を割り当てられている定義
           の性質を持たない時,その数はリシャール数であると呼ばれる.

  c パラドックス:「リシャール数である」という定義に数xが割り当てられているとき,xはリシャール数か否か?
    1) 「xはリシャール数」=>xは定義の性質を持つ=>xはリシャール数ではない
    2) 「xはリシャール数ではない」=>xは定義の性質を持たない=>xはリシャール数である
    ∴xはリシャール数でないときリシャール数であり,リシャール数であるときリシャール数ではない.
・第2章では数学的体系の「無矛盾性」や「完全性」が問題になる理由を学んだ.
・第3章ではこうした問題を研究するための数学の形式化を学んだ.
・第4章では『プリンキピア・マテマティカ』の方法と意図を学んだ.
・第5章では命題論理について「無矛盾性」や「完全性」が証明できることを学んだ.
・第6章では「無矛盾性」や「完全性」が証明できない体系が存在することを学んだ.
・第7章では実際にそのような体系が存在することをゲーデルに従って学ぶことになる.
・本書の水準では命題G( 「この命題は証明できない」という意味の命題)を構成するところが難しいだけである.

 さて,本章は3節構成です.まずA節でゲーデル数が導入され,証明過程を自然数の関係として表現する方法を学びます.B節ではDemとsubという2つの重要な記号を学びます.C節ではこの2つの記号を使って命題Gを構成する方法を学び,引き続きゲーデルの不完全性定理の証明の概要が示されます.
 ここではゲーデル数の有益性に驚いてください.不完全性定理という結果も大事ですが,コンピュータサイエンスとの関連では「ゲーデル数を利用した証明」という過程がもっと重要です.

A ゲーデル数













入門演習(柴田)                   
200267

報告者 H.S.

ナーゲル&ニューマン『ゲーデルは何を証明したか』白揚社,1999

7章 ゲーデルの証明  B 超数学の算術化

 

・計算のなかの表現の構造的性質に関するすべての超数学的言明は,この計算それ自体のなかに適切に反映されうる(ゲーデル)

 

 基本的アイデア

・計算のすべての表現に一つの数(ゲーデル数)が結びつけられるので,表現およびそれらの相互の関係についての超数学的言明は,対応する(ゲーデル)数とそれらのあいだの算術的関係についての言明として解釈できる

=>超数学を完全に算術化

 

超数学的言明を表わす算術式

 

 Dem(x,z)

 ≡ゲーデル数xをもつ式系列は,ゲーデル数zをもつ式の証明である

 

 例 @p⊃q

   A

   B

  ・式系列@ABは式Bの証明である

   =>ゲーデル数で考えてみる

 

 〜Dem(x,z)

 ≡ゲーデル数xをもつ式系列は,ゲーデル数zをもつ式の証明ではない

 

数の超数学的特徴づけ

 

 sub(m,13,m)

≡ゲーデル数mをもつ式から,そのなかにあるゲーデル数13の変項(=y)にmを表わす数詞を代入して得られる式のゲーデル数(式ではなく数)

 

 例@xy=s0

   =>ゲーデル数で考える

 例Axz=ss0

   =>ゲーデル数で考える






入門演習(柴田)                    2002年6月7日

報告者K.S.

ナーゲル・ニューマン『ゲーデルは何を証明したか』林 一訳,白揚社, 1999年

 

第7章 C ゲーデルの議論の核心

 

議論のあらすじ

ゲーデルの議論

i)「算術式Gは証明不可能」ということを表す算術式Gをつくった。

iiGはその形式的否定〜Gが証明可能であるとき、そしてそのときのみ証明可能であることを証明する。

iiiGは形式的に証明不可能だが、真なる算術式であることを証明した。

ivGは真であり、しかも形式的に証明不可能なので算術の公理は不完全である、すなわち、公理からすべての真理が演繹できるのではない。

v)算術の無矛盾性は確立不可能であることを証明。

 

ゲーデル式Gの構成

Dem(x,z)

[ゲーデル数xをもつ式系列は、ゲーデル数zをもつ式の証明ではない。]

(x)Dem(x,z)

[おのおののxについて、ゲーデル数xをもつ式系列は、ゲーデル数zをもつ式の証明ではない。][ゲーデル数zをもつ式は証明不可能である。]

(1)(x)Dem(x,sub(y,13,y))

[ゲーデル数sub(y,13,y)をもつ式は証明可能ではない。]

ここで(1)のゲーデル数をnとする

G(x)Dem(x,sub(n,13,n))

[ゲーデル数nをもつ式(見出し(1)の式)から、そのなかの変項ynの数詞を代入して得られた式は証明不可能である。]

☆ sub(n,13,n)Gのゲーデル数

Gは自分自身は証明不可能であると主張している

 

《ゲーデルの不完全性定理の教科書における証明》

 

第1不完全性定理 G¬G

教科書ではG¬Gだけを証明(p.151152

 aGが証明可能であるとする。すなわち

  (x)Dem(x,sub(n,13,n))・・・A

 bAは以下の式と同じであることが、初等論理学の変形規則から導かれる。

  ¬(x)¬Dem(x,sub(n,13,n))・・・¬G

以上。

 ※A式と¬G式との関係はA式とG[(x)¬Dem(x,sub(n,13,n))]との矛盾対当関係と考えて     

  もよい。

以上。

 

第2不完全性定理(「もし算術が無矛盾ならば、その無矛盾性は、算術の形式体系の中にその表示を見出せるような、いかなる超数学的推論によっても確立できない」)

教科書p.126129

 a「算術は無矛盾である」(p.7172,7577参照)

    (y)(x)¬Dem(x,y)・・・A

 b「算術は不完全である」

    (x)¬Dem(x,sub(n,13,n))・・・G(お馴染)

 c「もし算術が無矛盾ならば、それは不完全である。」

    (x)(x)¬Dem(x,y)(x)¬Dem(x,sub(n,13,n))・・・AG

 AGが真であることの証明は教科書では省略されている。

 dAが証明可能であると仮定すると

  A,AGよりGが導出[証明]される(p.68の分離規則参照)

 これはGが決定不可能すなわち証明不可能であることに矛盾する。

 したがって、Aは証明されない。

 ∴もし算術が無矛盾であれば(=Aの内容)、式Aは証明可能ではない。

 e「もし算術が無矛盾ならば、その無矛盾性は、算術の形式体系の中にその表示を見出せるような、いかなる超数学的推論によっても確立できない。」

以上。






《ゲーデルの不完全性定理について補足》
-ヒルベルトの体系
 第1不完全性定理≡体系の不完全性

 第2不完全性定理≡無矛盾な体系では無矛盾性を証明できない
-ゲンツェンの体系
 「標準化定理」から無矛盾性を証明(ただし問題あり)
-形式化のパラドックス
 
・現実世界の概念の形式言語による写し取り方,現実の形式化の方法を,正当化できる客観的で普遍的な基準が存在しない
  ∵形式的体系の不完全性

 ・形式化は現実世界をコピーするものであり,決着をつけるべきは,現実世界の論争であり人工世界の論争ではない.形式的体系を使っても論争が消え去る保証はない.


《参考文献(本格的に学ぶために)》
・ホフスタッター『ゲーデルエッシャーバッハ :あるいは不思議の環』白揚社, 1985.
・スマリヤン『ゲーデルの不完全性定理』高橋昌一郎訳,丸善,1996.
・田中一之他『数学基礎論講義』日本評論社,1997.