[論理学]戸田山本 3.11-3.12

戸田山和久『論理学をつくる』

名古屋大学出版会

私が『論理学をつくる』で論理学の勉強をする。

コンパクト性定理の証明が3章のクライマックス。論理式→論理式の集合ときて、ついに論理式の無限集合になった。むずかしい。一応ここだけは、証明を写経しておくことにする。

ようやっと3章が終わった。

■3.11 コンパクト性定理

• 3.11.1 コンパクト性定理とは
• 3.11.2 コンパクト性定理の証明・パートⅠ
• 3.11.3 コンパクト性定理の証明・パートⅡ

【定理20】コンパクト性定理(compactnesstheorem)

論理式の集合Tが充足可能である⇔Tのすべての有限部分集合が充足可能である。

以下ではこれを証明するよ。

■前置き

Tが有限集合のとき、上記が成り立つのは自明であることを示す。

• Tの有限部分集合のうち、最大のものがTになる。
• ならば「Tのすべての有限部分集合が充足可能である⇒Tが充足可能である」は明らか(T自身が「Tのすべての有限部分集合」に含まれる)。
• また「論理式の集合Tが充足可能である⇒Tのすべての有限部分集合が充足可能である。」も明らか(「Tのすべての有限部分集合」はTを充足する真理値割り当てのもとで、充足される)

またTが無限集合であっても、「論理式の集合Tが充足可能である⇒Tのすべての有限部分集合が充足可能である」は自明である(「Tのすべての有限部分集合」はTを充足する真理値割り当てのもとで、充足される)。

よって証明すべきことは、

「Tのすべての有限部分集合が充足可能である ⇒ 論理式の集合Tが充足可能である」

ということのみである。

また「すべての有限部分集合が充足可能である」は長いので、以下縮めて「有限充足可能(finitely sastisfiable)である」ということにする。

■証明方針

証明すべきことは、「Tのすべての有限部分集合が充足可能である⇒論理式の集合Tが充足可能である」

言い換えれば、

• 「論理式の無限集合Tについて」
• 「どのような有限部分集合をとってもそれぞれを充足する真理値割り当てが見つかる」ならば、
• 「T全体を充足するような真理値割り当てが存在する」

以下ではこれを以下のような手順で証明する。

1. 有限充足可能な論理式の集合Tは、ある都合のよい性質を持つ集合△に拡大できることを示す。
2. △を使うと簡単にTを充足する真理値割り当てをつくれることを示す。

■証明その1

• 1.有限充足可能な論理式の集合Tは、ある都合のよい性質を持つ集合△に拡大できることを示す。

論理式の集合Tが有限充足可能であると仮定する。

すべての論理式をA1, A2, A3, ..., Anのような形で順番に並べる。

論理式の無限集合{K0, K1, K2, ..., Kn}を以下のように定義する。

Kの定義

(1)K0=T

(2)Kn∪{An+1}が有限充足可能なら、Kn+1=Kn∪{An+1}とする。

Kn∪{An+1}が有限充足可能でないなら、Kn+1=Kn∪{￢An+1}とする。

この時、すべてのKnについて以下が成り立つことを証明しよう。

【補助定理20-1】

どのKnも有限充足可能である。

【補助定理20-1の証明】
(1) Tについての仮定よりK0(T)は有限充足可能である。
(2) Knが有限充足可能であると仮定する。このとき、
Kn+1(「Kn∪{An+1}」または「Kn∪{￢An+1}」)が有限充足可能である(☆)
と示せば、帰納法により補助定理20-1を証明することができる。
(3) (☆)の証明には、背理法を用いる。すなわち、(a)Knが有限充足可能であるのに、(b)Kn∪{An+1}が有限充足可能ではなく、(c)Kn∪{￢An+1}も有限充足可能ではないと仮定する。
(4) (b)より、Kn∪{An+1}の有限部分集合に充足可能でないものがあることになる。それはKnの有限部分集合Kn'に{An+1}を合わせた集合であるはずだ。なぜならば、{An+1}を含まないKnの有限部分集合は(a)より充足可能だからである。
(5) 従って、Kn'∪{An+1}が矛盾するようなKnの有限部分集合Kn'が存在する。
(6) 同様に(c)より、Kn''∪{￢An+1}が矛盾するようなKnの有限部分集合Kn''が存在する。
(7) (5)および(6)を変形すれば、「Kn'|=￢An+1」「Kn''|=An+1」を得られる。これは「Kn'∪Kn''」矛盾することを示している。
(8) しかし、Kn'∪Kn''はKnの部分集合なので、これは仮定(a)に反する。
(9) 仮定が誤りであったため、(☆)および補助定理20-1が証明された。■

以上より、論理式の無限集合{K0, K1, K2, ..., Kn}について、どのKnも有限充足可能であることが証明された。

ここでさらに{K0, K1, K2, ..., Kn}の合併集合を△とおく。△は以下のような性質を持つ。

【△の性質】

(1)T⊆△

(2)すべての論理式Aについて、Aか￢Aのいずれかが△に属す。

(3)△は有限充足可能である。

このうち(3)だけは証明しておく。

【(3)の証明】

△のどの有限部分集合△'も、それが含むAnのうち、番号が最大のものがあるはずである。その番号を仮にnとすると、△'はKnの部分集合である。補助定理20-1よりKnは有限充足可能であるから、Knの部分集合である△'も充足可能である。したがって△のどの有限部分集合も充足可能である。

■証明その2

• 2. △を使うと簡単にTを充足する真理値割り当てをつくれることを示す。

先に導入した△をもとにして、次のような原子式への真理値割り当てVをつくる。

【Vの定義】

原子式PiがVのもとで真である ⇔ Pi∈△

つまり、Vは△に含まれるすべての原子式だけに真を割り当てるような真理値割り当てである。このようなVについて以下が成り立つことを示す。

【補助定理 20-2】

任意の論理式Aについて、AがVのもとで真である ⇔ A∈△

これを示せば、Vは△に属するすべての式を充足することになる。T⊆△だから、Vは同時にTに属するすべての式を充足する。

【補助定理 20-2 の証明】
[Basis] Aが0個の結合子を含むとき、つまりAが原子式のとき、
AがVのもとで真である ⇔　A∈△ はVの定義より明らか。


[Induction step]
(1) K個以下の結合子を含む論理式については、AがVのもとで真である ⇔　A∈△ が成り立っていると仮定する。


(2) このとき、K+1個の結合子を含む論理式についても、AがVのもとで真である ⇔　A∈△ が成り立っていることを言う。
Subcase 1. K+1個の結合子を含む論理式Aが￢Bという形のとき、
 ￢BがVのもとで真である ⇔ K個の結合子を含む論理式BがVのもとで偽である
 ⇔ B∈△ ではない(帰納法の仮定より)
 ⇔ ￢B∈△ (△の性質(2)より)
Subcase 2. K+1個の結合子を含む論理式AがB∧Cという形のとき、
 B∧CがVのもとで真である
 ⇔ K個の結合子を含む論理式B, Cについて、BがVのもとで真であり、かつCがVのもとで真である
 ⇔ B∈△かつC∈△(帰納法の仮定より)
 このとき、B∧C∈△でないとすると、△の性質(2)より、￢B∧C∈△となる。
 すると、{B, C, ￢B∧C｝が△の部分集合となるが、この集合は矛盾している。これは△が有限充足可能であることに反する。
 したがって B∈△かつC∈△ ⇔ B∧C∈△ である。
Subcase 3. AがB∨Cという形のとき、
 B∨CがVのもとで真である
 ⇔ K個の結合子を含む論理式B, Cについて、BがVのもとで真であるか、またはCがVのもとで真である
 ⇔ B∈△あるいはC∈△(帰納法の仮定より)
 このとき、B∨C∈△でないとすると、△の性質(2)より、￢(B∨C)∈△となる。
 ド・モルガンの法則より、￢(B∨C) は ￢B∧￢C と同値。
 すると、{B, C, ￢B∧￢C)｝が△の部分集合となるが、この集合は矛盾している。これは△が有限充足可能であることに反する。
 したがって B∈△あるいはC∈△ ⇔ B∨C∈△ である。
Subcase 4. AがB→Cという形のとき、
 B→CがVのもとで真である
 ⇔ K個の結合子を含む論理式B, Cについて、BがVのもとで偽であるか、またはCがVのもとで真である
 ⇔ B∈△でないか、あるいはC∈△ (帰納法の仮定より)
 ⇔ ￢B∈△、あるいはC∈△ (△の性質(2)より)
このとき、B→C∈△でないとすると、△の性質(2)より、￢(B→C)∈△。
 ￢B∈△、あるいはC∈△の場合、{￢B, ￢(B→C)}{C, ￢(B→C)}のいずれかが△の部分集合となる。しかし、これらはどちらも矛盾する。これは△が有限充足可能であることに反する。
 したがって ￢B∈△、あるいはC∈△ ⇔ B∨C∈△ である。


(3) 以上より、すべての論理式Aについて、AがVのもとで真である ⇔　A∈△ が言えた。■

■ 証明終わり

上記により、次のことが言えた。

有限充足可能な論理式の集合Tは以下のような性質を持つ△に拡大できる。

【△の性質】

(1)T⊆△

(2)すべての論理式Aについて、Aか￢Aのいずれかが△に属す。

(3)△は有限充足可能である。

また以下のようなVについて、補助定理 20-2が言える。

【Vの定義】

原子式PiがVのもとで真である ⇔ Pi∈△

【補助定理 20-2】

任意の論理式Aについて、AがVのもとで真である ⇔ A∈△

Vは△を充足するため、△の部分集合であるTも充足する。

従って、「Tのすべての有限部分集合が充足可能である⇒論理式の集合Tが充足可能である」を証明することができた。

【定理20】コンパクト性定理(compactnesstheorem)

論理式の集合Tが充足可能である⇔Tのすべての有限部分集合が充足可能である。

は証明された。■

■ 3.12 メタ言語と対象言語をめぐって

• 3.12.1 メタ言語と対象言語を区別しよう
• 3.12.2 意味論的に閉じた言語とパラドクス
• 3.12.3 タルスキによる言語の階層化とうそつきのパラドクスについての最近の考え方

対象言語(object language)

論理の研究のためにつくられた人工言語Lのことだよ。Lには「P、Q、R」などの原子式や「∧、∨、￢、→」などの結合子が含まれているよ。

メタ言語(meta-language)

対象言語について話をするための言語だよ。本書では日本語や、「A、B」などの図式文字や、「⇔」などの便利な記号のことだよ。

この本では、対象言語とメタ言語を分けているから、両者を混同してはいけないよ。

意味論的に閉じた言語

対象言語としてもメタ言語としても使われる言語のこと。例えば日本語は意味論的に閉じた言語であるよ。意味論的に閉じた自己言語では、自己言及(self-reference)が可能になるよ。

自己言及はときに、意味論的パラドクス(semantic paradox)を生み出すよ。意味論的パラドクスの代表例は、うそつきのパラドクス(Liar paradox)だよ。

タルスキはうそつきのパラドクスを回避するために、意味論的に閉じた言語を考察の対象から外したよ。言語Lにおける真理の定義を別の言語ですることにしたよ。

こんな風な言語の階層化によってパラドクスは回避できたけど、最近はこれはやりすぎだったかもしれないと言われているよ。

(1)自己言及には無害なものも数多くあるよ。

(2)また、自己言及的な文を用いなくてもパラドクスをつくることができるよ。

つまり、パラドクスは文ではなく、文の使い方によって生み出されるってことだよ。

そこで最近の論理学者は意味論的に閉じた言語でパラドクスを回避する方法を模索しているよ。でも本書ではそこまでフォローできないよ。