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

トートロジーの作り方

前回の記事に続いてトートロジーの作り方を考えてみた。

1. A と B がトートロジーの時 A -> B はトートロジーである。
2. A がトートロジーの時 ¬A は恒偽命題である。また、A の二重否定 ¬¬A はトートロジーである。
3. A がトートロジーの時そのプレースホルダーを任意の命題で置き換えたものはトートロジーである。
4. A かつ A -> B がトートロジーの時、B はトートロジーである。

これらは、真理値関数や真理表によって確認することができる。ルール 3 で特に注目すべきは、プレースホルダーの A B を置き換えるのに A = C -> D, B = ¬C のように、A と B に現れる原子命題が重複したり、否定 ¬ を含んでいても構わないということだ。また、公理系の演繹では上のルールの 2, 4 が採用されている。もし、1, 2 も演繹と見なせば、演繹はトートロジーの性質と一致する。

これらのルールを適用すると、任意のトートロジー A, B から無限にトートロジーを作り出すことができる。また、これらのルールで作られるトートロジーは公理系で演繹された定理全てを含んでいる。

しかし、それにも関わらず任意のトートロジーが同時に公理系でも演繹されたものであるかどうかを言うことはできない。上のルールはトートロジーからトートロジーを生成するためのルールであるが、ある命題がトートロジーであるかどうかは、その命題の内部構造による真理値表の性質によるものであるからだ。

つまり、任意の命題がトートロジーであるか否かは、真理値表によって判定できるが、そのトートロジーがトートロジーで構成されており、それを公理にまでたどることができるかを証明することができないからだ。例えば、

A -> (B -> A)

はトートロジーであるが、だからといって A や B -> A がトートロジーであるわけではない。

そのため、完全性定理の証明でも任意の構造的なトートロジーが公理から演繹されたものだというような直接的な証明の仕方はしていない。完全性定理のポイントは、

命題 A が証明不可能であれば、それはトートロジーではない。

ということを証明することだ。それが証明できればその対偶の「命題 A がトートロジーであれば証明可能である。」ということが言える。

命題 A はそれを構成する複合命題の性質によって、トートロジーの場合と、恒偽命題の場合と、原子命題の真偽値によって命題 A の真理値が変わる場合の3つがある。このうち恒偽命題が定理になりえないのは明らかだ。なぜなら定理によって演繹された命題は全てトートロジーであるからだ。同様に、原子命題の値によって真理値が変わる命題も定理ではない。したがって、問題は命題 A がトートロジーであって、証明不可能であるという場合が起こりえるかどうかということになる。

ここで問題になるのは、命題 A が証明不可能であるということをどうして知るかということだ。上でも述べたように、命題 A の内部構造からその証明可能性を知ることはできない。したがって、

Σ |- A の時 Σ, ¬A は矛盾する

という定理を利用する。つまり、¬A を核としてこれと矛盾しない命題を集めて Σ = {¬A, A1, A2, ... } という命題の集合を作る。この時無矛盾の Σ が存在すれば命題 A が証明不可能であることが言える。Σ の命題は命題の文法で作成されたものを網羅したものを用いるので全ての命題をカバーしているし、無矛盾かどうかは、公理系からの演繹で確かめることができる。したがって Σ が無矛盾であれば命題 A が証明できないと言える。

だが、残念ながら、この仮定には穴がある。それは、公理系からの演繹が全ての命題(命題の文法規則から作られる複合命題)の無矛盾性を判別できるという仮定である。つまり、ウカシェビッチの3つの公理から演繹されるトートロジーは命題の内部構造から判断できるトートロジー全てを網羅しているという仮定だ。しかし、それについての証明は教科書にはない。例えば、ウカシェビッチの公理のうち対偶に関するものを除いたら、残りの公理では否定を含む命題のトートロジーを演繹できない。したがって、したがって、公理が全てのトーロジーを生成できることの証明がない限り完全性定理の証明は単なる同語反復でしかない。

おそらく、これはまだ勉強が足りないせいなのだろうが、素人に完全性定理が承服できない理由の一つだ。

by tnomura9 | 2016-09-02 06:18 | 考えるということ | Comments(0)
<< トートロジーの等価変換 全ての命題からトートロジーを作... >>