【連載:命題論理6】コンパクト性定理とか

コンパクト性定理

完全性まで示したので,コンパクト性定理を簡単に示すことができます.

極大無矛盾集合の構成によって完全性を示すことのメリットの一つです.新井本では完全性定理を「トートロジーならば証明可能」の形で示していたので,このままでは有限の論理式の集合\(\Gamma\)についてしか\( \Gamma \vDash \varphi \iff \Gamma \vdash \varphi \)が成り立たず,コンパクト性は別に証明する必要がありました.コンパクト性によって一般の\( \Gamma \)に完全性を持ち上げるというのが新井本の手法です.

ところが,極大無矛盾集合を構成してしまえば\( \Gamma \)は最初から有限である必要がないので,コンパクト性定理は系になります.

ではいくつか準備をします.注意としては,「充足可能」と「モデルを持つ」は同じことです.文脈であてはまりのいいように言い換えていますが,同じ意味であることに注意してください.

補題6-1
論理式の集合\( \Gamma \)がモデルを持つならば無矛盾である.

(証明)
\( \Gamma \)がモデルを持つことよりある\(\nu\)が存在して\(\nu \vDash \Gamma\)となる.このとき\( \Gamma \vdash \bot \)であるとすると健全性定理より\( \Gamma \vDash \bot \). すなわち,\( \nu(\bot) = 1 \)となる.これは付値の定義に矛盾する.よって,\( \Gamma \not\vdash \bot \)であり,すなわち\(\Gamma\)は無矛盾.

この補題とモデルの存在定理より, 「\( \Gamma \)が無矛盾 \(\iff\) \( \Gamma \)がモデルを持つ」がわかりました.

定義(有限充足可能)
論理式の集合\( \Gamma \)の任意の有限部分集合\( \Gamma_0 \subset \Gamma\)が充足可能であるとき\( \Gamma \)は有限充足可能であるという.

では,コンパクト性定理を示しましょう.

定理(コンパクト性定理)
\( \Gamma\)が有限充足可能ならば充足可能.

(証明)
対偶を示す.モデルを持たないことと無矛盾であることが同値であるから次を示せばよい,
\( \Gamma \vdash \bot \)ならばある有限部分\( \Gamma_0 \subset \Gamma\)について\( \Gamma_0 \vdash \bot \).
ところが,これは証明の定義より自明.

選択公理とコンパクト性定理

選択公理があればコンパクト性定理は位相空間論的に示せます.というか,コンパクトという言葉がそもそも位相空間の言葉ですから名前の背景がここに書いたことにあたるということだと思います.

素論理式の集合が可算の場合には可算選択公理くらいで大丈夫だと思います(もしかしたらいらないかもしれませんがいつか確かめます. 極大無矛盾集合の構成において\(I\)が可算の時には選択公理を一切必要としないように, Tychonoffの定理も可算直積に関しては選択公理の使用を回避する証明方法があるかもしれません. 知ってる方がはコメントくださると嬉しいです).

位相空間論ではコンパクトであることは次のように言い換えられます.

定義(有限交叉性)
集合\(S\)の部分集合族\(\mathcal{F}\)が有限交叉性を持つとは,任意の\(\mathcal{F}\)の有限部分集合\( \{S_1, S_2, \cdots, S_n\} \)が,\(S_1 \cap S_2 \cap \cdots \cap S_n \neq \emptyset \)を満たすことである.

位相空間\(X\)がコンパクト\( \iff \)
\(X\)の任意の閉集合族\(\mathcal{C}\)について有限交叉性を持つならば\( \bigcap_{C \in \mathcal{C}} C \neq \emptyset. \)

ではコンパクト性定理を示します.

定理(コンパクト性定理)
\( \Gamma\)が有限充足可能ならば充足可能.

(証明)
素論理式の集合\(I\)について,任意の付値は\(2^I\)の元である. \(2\)に離散位相を入れるとコンパクトとなりTychonoffの定理より\( 2^I\)もコンパクトである.
任意の\( \varphi \in \Gamma\)を固定し,\( F_{\varphi} := \{ \nu \in 2^I | \nu(\varphi) = 1 \} \)とする.このとき,\( \Gamma\)の有限充足可能性より\( \{ F_{\varphi} | \varphi \in \Gamma \} \)は有限交叉性を持つ.したがって,
\( \quad \bigcap_{\varphi \in \Gamma} F_{\varphi} \neq \emptyset, \)
が成り立つ. すなわち,すべての\( \varphi \in \Gamma\)を一斉に充足する付値が存在するから\( \Gamma \)は充足可能.

参考文献

[1] ケネス・キューネン, キューネン数学基礎論講義, 日本評論社,2016.

コメントを残す