知識は永遠の輝き

学問全般について語ります

ゲーデルの定理-4.1- 対角化定理(この論理式は証明できない)

2015-12-13 07:35:52 | 数学基礎論/論理学
共通参考文献はこちら
前回からの続き

 【再掲】式3.3-1 U⇔¬Bew(~~)

 さてこの式を満たす確定文が存在することの証明にはゲーデルの対角化定理と呼ばれる、より一般的な定理が使われます。

ゲーデルの対角化定理(前原[Ref)-p130]の定理8.3)
 任意の1変数論理式R(x)について、次の式を満たす確定文が存在する。
 式4.1-1 A⇔R(a) ただしa=~~

 ごらんのように、この定理は任意のR(x)について成り立ちますので、R(x)として¬Bew(x)をとれば、ただちに確定文の存在証明になります。対角化定理の証明は長くなるので、ひとまず証明はできたものとして確定文の意味を少し書いてみましょう。

 は具体的には次の式になります。ここで2項関数Sb(b,a)と1項関数Z(n)は後ほど対角化定理の証明の中で詳しく登場します。

式4.1-2 ¬Bew(Sb(g,Z(g)))
   g=~¬Bew(Sb(x,Z(x)))~
   1項関数Z(n)は、自然数nの定数項のゲーデル数を返す関数
   2項関数Sb(b,a)は、ゲーデル数bである自由文B(x)の変数記号に、
     ゲーデル数aである対象式を代入した論理式B(A)
     のゲーデル数を返す関数

 ここでk=~~=~¬Bew(Sb(g,Z(g)))~ とおけば、Sb(g,Z(g))が返す値は、
  ゲーデル数gである論理式、つまり¬Bew(Sb(x,Z(x)))、の変数記号に、
  gを記述する定数項を代入した論理式、つまり¬Bew(Sb(g,Z(g)))、のゲーデル数
  すなわち~~=kです。
 よって、次の式が証明できます。

式4.1-3a ¬Bew(Sb(g,Z(g)))¬Bew(k) k=~~
 すなわち
式4.1-3b ¬Bew(k) k=~~


 さてBew(a)は「ゲーデル数aである論理式は証明できる」という意味を持ちましたが、ここで¬Aの証明可能性、自然数関係Bew(a)、¬Bew(a)、Bew(_a)、¬Bew(_a)の真偽、およびBew(a)¬Bew(a)の証明可能性について4つの場合に整理できます。なお、Nga=~¬A~ です。






場合¬ABew(a)¬Bew(a)Bew(Nga)¬Bew(Nga)Bew(a)¬Bew(a)
|--- |-x- |--- |-x-
|-x- |--- |-x- |---
|-x- |-x- |-x- |-x-
|--- |--- 矛盾矛盾矛盾矛盾 |--- |---


 場合4は矛盾ですから除くとして、場合1,2,3について¬Aに関する分類とBew(a)¬Bew(a)に関する分類とが一致するというのが前回で示されたことでした。
 が確定文なら真理値も証明可能性も一通りであり、3つの場合のいずれかひとつになります。が自由文すなわち自由変数を持つA(x)ならxの値により3つの場合のいずれにも成り得ます。そして場合1と2だけのときには、「|--- A(x)」という論理式世界の命題に対応する「Bew(a)」という自然数世界の関係が「Bew(a)」という論理式により表現されている、ということになります。そして場合3に当たる論理式がひとつもなければ、この公理系は統語論的に完全ということになります。しかし自然数の理論を含む公理系ではという場合3に属する確定文が存在したのでした。

 さて式4.1-2をよく見れば、以下の各式の「意味」が次のようになります。
   Sb(x,Z(x))  式に、そのゲーデル数xを代入した式のゲーデル数を記述。
     すなわち、式について命題Xが成り立つ、という意味を持つ。
   ¬Bew(Sb(x,Z(x))) 「式について命題Xである」という(命題を記述する)式は証明できない、という意味を持つ。

 つまりSb(x,Z(x))は自身について述べるような自己言及文となっています。

 さらに式4.1-3bをよく見れば、という論理式は「は証明できない」という意味を持つことがわかります。これは「この文は嘘である」というようなパラドックス的自己言及文であるのです。しかしは「嘘である(真ではない)」とは言っておらず「証明できない」と言っているだけなので矛盾は生まないのです。なぜなら表の通り第3の場合もあるからです。

 表でわかる通り、「は証明できない」という論理式世界の命題が成り立つならば、自然数関係¬Bew(~~)は真のはずです。が、Bew(~~)は証明できません。もちろん¬Bew(~~)も証明できないので何も矛盾は起きません。そして証明できなくても矛盾しない大きな要因はつまり¬Bew(k)¬∃yB(y,k)という形であること、つまり∀y¬B(y,k)という形であることです。まさに「すべてのカラスが白くない」ことは確認できないということです。

 さて自己言及文の観点からはスマリヤンの本に詳しい話がありますので、次回にその話を少しします。

コメント    この記事についてブログを書く
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする
« ゲーデルの定理-参考文献- | トップ | ゲーデルの定理-4.2A- 対角化... »
最新の画像もっと見る

コメントを投稿

数学基礎論/論理学」カテゴリの最新記事