共通参考文献はこちら
前回からの続き
【再掲】式3.3-1 U⇔¬Bew(~U~)
さてこの式を満たす確定文Uが存在することの証明にはゲーデルの対角化定理と呼ばれる、より一般的な定理が使われます。
ゲーデルの対角化定理(前原[Ref)-p130]の定理8.3)
任意の1変数論理式R(x)について、次の式を満たす確定文Aが存在する。
式4.1-1 A⇔R(a) ただしa=~A~
ごらんのように、この定理は任意のR(x)について成り立ちますので、R(x)として¬Bew(x)をとれば、ただちに確定文Uの存在証明になります。対角化定理の証明は長くなるので、ひとまず証明はできたものとして確定文Uの意味を少し書いてみましょう。
Uは具体的には次の式になります。ここで2項関数Sb(b,a)と1項関数Z(n)は後ほど対角化定理の証明の中で詳しく登場します。
式4.1-2 U≡¬Bew(Sb(g,Z(g)))
g=~¬Bew(Sb(x,Z(x)))~
1項関数Z(n)は、自然数nの定数項nのゲーデル数を返す関数
2項関数Sb(b,a)は、ゲーデル数bである自由文B(x)の変数記号xに、
ゲーデル数aである対象式Aを代入した論理式B(A)、
のゲーデル数を返す関数
ここでk=~U~=~¬Bew(Sb(g,Z(g)))~ とおけば、Sb(g,Z(g))が返す値は、
ゲーデル数gである論理式、つまり¬Bew(Sb(x,Z(x)))、の変数記号xに、
gを記述する定数項gを代入した論理式、つまり¬Bew(Sb(g,Z(g)))、のゲーデル数
すなわち~U~=kです。
よって、次の式が証明できます。
式4.1-3a ¬Bew(Sb(g,Z(g)))⇔¬Bew(k) k=~U~
すなわち
式4.1-3b U⇔¬Bew(k) k=~U~
さてBew(a)は「ゲーデル数aである論理式Aは証明できる」という意味を持ちましたが、ここでA、¬Aの証明可能性、自然数関係Bew(a)、¬Bew(a)、Bew(_a)、¬Bew(_a)の真偽、およびBew(a)、¬Bew(a)の証明可能性について4つの場合に整理できます。なお、Nga=~¬A~ です。
場合4は矛盾ですから除くとして、場合1,2,3についてA、¬Aに関する分類とBew(a)、¬Bew(a)に関する分類とが一致するというのが前回で示されたことでした。
Aが確定文なら真理値も証明可能性も一通りであり、3つの場合のいずれかひとつになります。Aが自由文すなわち自由変数を持つA(x)ならxの値により3つの場合のいずれにも成り得ます。そして場合1と2だけのときには、「|--- A(x)」という論理式世界の命題に対応する「Bew(a)」という自然数世界の関係が「Bew(a)」という論理式により表現されている、ということになります。そして場合3に当たる論理式がひとつもなければ、この公理系は統語論的に完全ということになります。しかし自然数の理論を含む公理系ではUという場合3に属する確定文が存在したのでした。
さて式4.1-2をよく見れば、以下の各式の「意味」が次のようになります。
Sb(x,Z(x)) 式Xに、そのゲーデル数xを代入した式のゲーデル数を記述。
すなわち、式Xについて命題Xが成り立つ、という意味を持つ。
¬Bew(Sb(x,Z(x))) 「式Xについて命題Xである」という(命題を記述する)式は証明できない、という意味を持つ。
つまりSb(x,Z(x))は自身について述べるような自己言及文となっています。
さらに式4.1-3bをよく見れば、Uという論理式は「Uは証明できない」という意味を持つことがわかります。これは「この文は嘘である」というようなパラドックス的自己言及文であるのです。しかしUは「嘘である(真ではない)」とは言っておらず「証明できない」と言っているだけなので矛盾は生まないのです。なぜなら表の通り第3の場合もあるからです。
表でわかる通り、「Uは証明できない」という論理式世界の命題が成り立つならば、自然数関係¬Bew(~U~)は真のはずです。が、Bew(~U~)は証明できません。もちろん¬Bew(~U~)も証明できないので何も矛盾は起きません。そして証明できなくても矛盾しない大きな要因はUつまり¬Bew(k)が¬∃yB(y,k)という形であること、つまり∀y¬B(y,k)という形であることです。まさに「すべてのカラスが白くない」ことは確認できないということです。
さて自己言及文の観点からはスマリヤンの本に詳しい話がありますので、次回にその話を少しします。
前回からの続き
【再掲】式3.3-1 U⇔¬Bew(~U~)
さてこの式を満たす確定文Uが存在することの証明にはゲーデルの対角化定理と呼ばれる、より一般的な定理が使われます。
ゲーデルの対角化定理(前原[Ref)-p130]の定理8.3)
任意の1変数論理式R(x)について、次の式を満たす確定文Aが存在する。
式4.1-1 A⇔R(a) ただしa=~A~
ごらんのように、この定理は任意のR(x)について成り立ちますので、R(x)として¬Bew(x)をとれば、ただちに確定文Uの存在証明になります。対角化定理の証明は長くなるので、ひとまず証明はできたものとして確定文Uの意味を少し書いてみましょう。
Uは具体的には次の式になります。ここで2項関数Sb(b,a)と1項関数Z(n)は後ほど対角化定理の証明の中で詳しく登場します。
式4.1-2 U≡¬Bew(Sb(g,Z(g)))
g=~¬Bew(Sb(x,Z(x)))~
1項関数Z(n)は、自然数nの定数項nのゲーデル数を返す関数
2項関数Sb(b,a)は、ゲーデル数bである自由文B(x)の変数記号xに、
ゲーデル数aである対象式Aを代入した論理式B(A)、
のゲーデル数を返す関数
ここでk=~U~=~¬Bew(Sb(g,Z(g)))~ とおけば、Sb(g,Z(g))が返す値は、
ゲーデル数gである論理式、つまり¬Bew(Sb(x,Z(x)))、の変数記号xに、
gを記述する定数項gを代入した論理式、つまり¬Bew(Sb(g,Z(g)))、のゲーデル数
すなわち~U~=kです。
よって、次の式が証明できます。
式4.1-3a ¬Bew(Sb(g,Z(g)))⇔¬Bew(k) k=~U~
すなわち
式4.1-3b U⇔¬Bew(k) k=~U~
さてBew(a)は「ゲーデル数aである論理式Aは証明できる」という意味を持ちましたが、ここでA、¬Aの証明可能性、自然数関係Bew(a)、¬Bew(a)、Bew(_a)、¬Bew(_a)の真偽、およびBew(a)、¬Bew(a)の証明可能性について4つの場合に整理できます。なお、Nga=~¬A~ です。
場合 | Aは | ¬Aは | Bew(a) | ¬Bew(a) | Bew(Nga) | ¬Bew(Nga) | Bew(a) | ¬Bew(a) |
1 | |--- | |-x- | 真 | 偽 | 偽 | 真 | |--- | |-x- |
2 | |-x- | |--- | 偽 | 真 | 真 | 偽 | |-x- | |--- |
3 | |-x- | |-x- | 偽 | 真 | 偽 | 真 | |-x- | |-x- |
4 | |--- | |--- | 矛盾 | 矛盾 | 矛盾 | 矛盾 | |--- | |--- |
場合4は矛盾ですから除くとして、場合1,2,3についてA、¬Aに関する分類とBew(a)、¬Bew(a)に関する分類とが一致するというのが前回で示されたことでした。
Aが確定文なら真理値も証明可能性も一通りであり、3つの場合のいずれかひとつになります。Aが自由文すなわち自由変数を持つA(x)ならxの値により3つの場合のいずれにも成り得ます。そして場合1と2だけのときには、「|--- A(x)」という論理式世界の命題に対応する「Bew(a)」という自然数世界の関係が「Bew(a)」という論理式により表現されている、ということになります。そして場合3に当たる論理式がひとつもなければ、この公理系は統語論的に完全ということになります。しかし自然数の理論を含む公理系ではUという場合3に属する確定文が存在したのでした。
さて式4.1-2をよく見れば、以下の各式の「意味」が次のようになります。
Sb(x,Z(x)) 式Xに、そのゲーデル数xを代入した式のゲーデル数を記述。
すなわち、式Xについて命題Xが成り立つ、という意味を持つ。
¬Bew(Sb(x,Z(x))) 「式Xについて命題Xである」という(命題を記述する)式は証明できない、という意味を持つ。
つまりSb(x,Z(x))は自身について述べるような自己言及文となっています。
さらに式4.1-3bをよく見れば、Uという論理式は「Uは証明できない」という意味を持つことがわかります。これは「この文は嘘である」というようなパラドックス的自己言及文であるのです。しかしUは「嘘である(真ではない)」とは言っておらず「証明できない」と言っているだけなので矛盾は生まないのです。なぜなら表の通り第3の場合もあるからです。
表でわかる通り、「Uは証明できない」という論理式世界の命題が成り立つならば、自然数関係¬Bew(~U~)は真のはずです。が、Bew(~U~)は証明できません。もちろん¬Bew(~U~)も証明できないので何も矛盾は起きません。そして証明できなくても矛盾しない大きな要因はUつまり¬Bew(k)が¬∃yB(y,k)という形であること、つまり∀y¬B(y,k)という形であることです。まさに「すべてのカラスが白くない」ことは確認できないということです。
さて自己言及文の観点からはスマリヤンの本に詳しい話がありますので、次回にその話を少しします。
※コメント投稿者のブログIDはブログ作成者のみに通知されます