人気ブログランキング | 話題のタグを見る

命題論理の完全性定理の焦点

命題論理の完全性の定理の仕組みがもう一つわかった感じがしなかったので考えてみた。これは、出典はなく、管理人の考えなので間違っているかもしれない。

命題論理の完全性とは、A -> A のような命題が証明可能の時はトートロジーであり、トートロジーの時は証明可能であるということだ。

A -> A がトートロジーかどうかは真理値表や真理値関数で直接に計算できる。また、証明可能な命題の証明に現れる命題は全て定理であり、定理はトートロジーなのは真理値関数の性質から証明できる。従って、A -> A が証明可能であればそれがトートロジーであるのは比較的簡単にわかる。

問題は、証明可能な命題(定理)が全てトートロジーであると証明することだ。上で述べたように A -> A のような命題がトートロジーであるのは機械的な計算でわかる。また、A -> A が定理であればその証明を求めることは可能だ。しかし A ∨ B のような任意の命題が定理かどうかをどうやって判断するかは難しい。

そうであれば、証明可能な定理のみを要素とする集合が定義できれば、その集合の要素の真理値を T とする真理値関数を定義するのは簡単だろう。従って命題論理の焦点は、証明可能な定理のみを集めた集合を作る方法は何かということになる。

それでは、任意の命題 A が定理であるかどうかを判別する方法はどうすればいいのだろうか。A -> A が定理であればその証明を発見することはいつでも可能であるとしよう。しかし、命題 A が定理ではない時にそれが定理でないことを証明する方法はどうすればいいのだろうか。定理であるというのは証明という命題の列を発見すればいいが、定理でないということを証明するためにはそのような命題の列が存在しないことを証明しなければならない。幸い命題 A が定理でない時に関連する命題論理の補題がある。それは次のようなものだ。

Σ∪ {¬A} が矛盾する ⇔ Σ|- A

これから、

命題 A が定理かどうかを、Σ∪ {¬A} が矛盾するという命題に置き換えることができる。つまり命題 A が定理かどうかは、

{¬A} |- ¬(p0 -> p0)

という問題に変えることができる。命題 A が定理でない時証明がないことを証明する場合は、あらゆる可能性を考えなければいけないので選択肢が膨大になり不可能であるが、¬(p0 -> p0) の証明なら求められる。従って、{¬A} が矛盾する場合、命題 A が証明可能なので、命題 A が証明可能ではないという命題は、

{¬A} は無矛盾である

という命題に置き換えることができる。(無矛盾であるというのも否定の証明だが、{¬A} |- ¬(p0 -> p0) で無矛盾性は否定できる。)同じような判別命題を使えば命題 A0 について、

{¬A, A0} が無矛盾であることも証明可能である。この場合は ¬A と A0 が証明可能な命題となる。この操作を繰り返すことによって、¬A を含み無矛盾な命題を含む無限集合 Σ を作ることができる。

Σ = {¬A, A0, A1, A2, ... }

Σの要素は全て証明可能だから、任意の n について

|- An

である。また、この時、証明は省略するが A ∈ Σ か ¬A ∈ Σ のどちらかのみが成立する。

証明可能な命題はトートロジーだから、An もトートロジーである。この時、真理値関数 V(x) を次のように定義すると、これは命題の真理値関数の条件を満たしている。

V(A) = T ⇔ A ∈ Σ

つまり、証明可能な命題だけからなる命題の集合を作ることができたため、それがトートロジーであることを証明できるのだ。それでは、この V(x) を使って定理ではない命題 A の真理値を求めると A /∈ Σなので、

V(A) = F

となる。すなわち証明可能な定理はトートロジーである。

.... とここまで書いてきて、どうしても違和感が拭えないのに気がついた。

この証明は「証明可能な命題」という表現を単に「無矛盾な命題」に置き換えただけではないかということだ。すなわち、証明可能な命題の全体を求める明確なアルゴリズムが提示されていない。公理が決まれば、証明可能な命題は決まってくるはずだから(それは有限個の原子命題と論理記号の配列になるから)、単に「証明可能な命題の集合」Σ を考えることができる。その中に矛盾した命題があれば、それらから矛盾が証明できるはずだから、Σ は無矛盾でなくてはならない。またΣの要素 A の否定 ¬A が Σ に含まれていれば Σ は矛盾するので A ∈ Σ ならば ¬A /∈ Σ である。要は、そのような無矛盾な集合 Σ に真理関数 V を定義できることを示せば済む。そのような真理関数が命題の直接計算から得られる真理値と一致すれば、トートロジーと証明可能性の同値が証明できる。

トートロジーと証明可能性は、 例えば、A -> A という論理式が同じものを共有している。トートロジーはこの論理式の構造から証明できるが、そうであれば、証明可能性についても A -> A という命題の構造から証明できないといけないのではないかということだ。A -> A はその構造からトートロジーである。また同時に A -> A はその構造から証明可能と言えなくてはならないないのではないだろうか。この場合は当然トートロジーと証明可能性は同値である。もちろん A -> A の証明は1通りではなく無数に存在するから、それらの同値関係を考えないといけないから大変だろうが。

おそらく何かを誤解しているのだろうが、何となく、納得できない。

追記

命題 A が定理ではない場合はふた通りの場合がある。一つは ¬A が定理である場合と、A も ¬A も定理ではない場合である。完全性定理の論証は ¬A が定理である場合について行われるようだ。¬A が定理でない時、これを含む無矛盾な命題の集合は作れないので Σ = φである。すなわち、命題 A が定理でない時 V(A) = F。結局のところ 命題 A が定理でない場合は常に V(A) = F である。

by tnomura9 | 2016-08-15 21:20 | 考えるということ | Comments(0)
<< 定理の構造 命題論理記事リスト >>