文献あり

3つの方法による命題論理のコンパクト性定理の証明

443

この著者は初心者として投稿しています。間違いや考慮が足りていない点が含まれている可能性が高いです。見つけたらコメント欄で優しく指摘してあげましょう。

はじめに

本稿では,命題論理の完全性定理,超限帰納法, Tychonoffの定理から命題論理のコンパクト性定理を証明します.前提知識として,学部3～4年次程度の公理的集合論の知識（主に順序数,整列可能定理,超限帰納法）と学部2～3年次程度の位相空間論（主にTychonoffの定理）の知識を仮定しますので,必要であれば例えばKunenやMoritaを参考にしてください.

命題論理のコンパクト性定理

命題論理の用語

命題論理のコンパクト性定理の証明に必要な用語を確認します.

命題論理の論理記号(logical symbol)とは, $\neg, \lor, \land, \to$ の4つをいう.命題論理の素論理式とは,記号 $p, q, r, \dots$ をいい,素論理式全体の集合を $PFml$ と表す.

論理式とは,次の規則で構成される有限列をいう.

素論理式は論理式である.
論理式 $A, B$ に対し, $\neg A, A \lor B, A \land B, A \to B$ は論理式である.

論理式全体の集合を $Fml$ と表す.

結合の強さは $\neg, \land, \lor, \to$ の順に弱くなるものとする.

写像 $v : PFml \to 2$ を付値という.

付値 $v : PFml \to 2$ について,写像 $\overset{―}{v} : Fml \to 2$ を次で定める.

$\overset{―}{v} (p) = v (p), p \in PFml .$
$\overset{―}{v} (\neg A) = 1 - \overset{―}{v} (A), A \in Fml .$
$\overset{―}{v} (A \to B) = max {1 - \overset{―}{v} (A), \overset{―}{v} (B)}, A, B \in Fml .$

このとき,付値 $v$ における論理式 $A$ の値 $\overset{―}{v} (A)$ を $A$ の真理値という. $v ⊨ A$ とは $\overset{―}{v} (A) = 1$ のことをいう.

論理式 $A$ がトートロジーであるとは,任意の付値 $v$ に対して, $v (A) = 1$ を満たすことをいう.このとき, $⊨ A$ とかく.

論理式の集合 $T$ が充足可能であるとは,ある付値 $v$ が存在して,任意の $A \in T$ に対して $v ⊨ A$ を満たすことをいう. $T$ が有限充足可能であるとは, $T$ の任意の有限部分集合 $S$ が充足可能であることをいう.

論理式の集合 $T$ と論理式 $A$ に対して, $A$ は $T$ から証明可能であるとは,次の規則で定義される.

$T$ の元とトートロジー公理は $T$ から証明可能である.
$A$ と $A \to B$ が $T$ から証明可能であれば, $B$ は $T$ から証明可能である(基本推論).

$A$ が $T$ から証明可能であるとき, $T ⊢ A$ とかく.

本稿ではあまり本質的ではないので,トートロジー公理とはトートロジーのことであるとみなしても構いません.

論理式の集合 $T$ が矛盾するとは, $T ⊢ A$ かつ $T ⊢ \neg A$ なる論理式 $A$ が存在することをいう. $T$ が無矛盾であるとは, $T$ は矛盾しないことをいう.

完全性定理を用いた証明

最も有名な方法は命題論理の完全性定理を用いた証明です.命題論理の完全性定理とは,次の定理をいいます.

命題論理の完全性定理

論理式の集合 $T$ に対して,次は同値である.

$T$ は充足可能である.
$T$ は無矛盾である.

ここではこの定理の証明は省略します.証明は,例えばTanakaをご覧ください.それでは,命題論理のコンパクト性定理の証明を行います.

命題論理のコンパクト性定理

論理式の集合 $T$ に対して,次は同値である.

$T$ は充足可能である.
$T$ は有限充足可能である.

この定理のうち, $(1) ⟹ (2)$ は明らかですので, $(2) ⟹ (1)$ を示します.

もし $T$ が充足可能でないとする.このとき,命題論理の完全性定理より, $T$ は矛盾する.よって, $T ⊢ A$ かつ $T ⊢ \neg A$ なる論理式 $A$ が存在する.これより, $T$ の有限部分集合 $S$ で, $S ⊢ A$ かつ $S ⊢ \neg A$ なるものが存在する.よって, $S$ は矛盾しているから,再び命題論理の完全性定理より $S$ は充足可能でない.従って, $T$ は有限充足可能でない. $◻$

超限帰納法を用いた証明

次に,超限帰納法を用いて命題論理のコンパクト性定理の証明を行います.証明はEndertonを参考にしています.

命題論理のコンパクト性定理(再掲)

論理式の集合 $T$ に対して,次は同値である.

$T$ は充足可能である.
$T$ は有限充足可能である.

整列可能定理より,論理式全体の集合 $F = Fml$ は整列可能である.このとき, $F$ と順序同型な順序数 $ξ$ が存在する.これより, $F = {A_{α} ∣ α < ξ}$ と表せる.超限再帰的に,論理式の集合 $T_{α} (α \leq ξ)$ を次の規則で定める.
$\begin{aligned} T_{0} & = T . \\ T_{α + 1} & = {\begin{cases} T_{α} \cup {A_{α}} & T_{α} \cup {A_{α}} が有限充足可能である. \\ T_{α} \cup {\neg A_{α}} & T_{α} \cup {A_{α}} が有限充足可能でない. \end{cases} \\ T_{α} & = ⋃_{β < α} T_{β} & α は極限順序数 . \end{aligned}$

すべての $α \leq ξ$ に対して, $T_{α}$ は有限充足可能であることを超限帰納法により示そう.

まず, $T_{0} = T$ なので,仮定より $T_{0}$ は有限充足可能である.次に, $α < ξ$ に対して, $T_{α}$ は有限充足可能であると仮定する.もし $T_{α} \cup {A_{α}}$ が有限充足可能であるとき,明らか.また, $T_{α} \cup {A_{α}}$ が有限充足可能でないとき, $T_{α} \cup {\neg A_{α}}$ は有限充足可能である.よって, $T_{α + 1}$ は有限充足可能である.最後に, $γ \leq ξ$ を極限順序数として,すべての $α < γ$ に対して $T_{α}$ が有限充足可能であると仮定する.このとき, $S \subset T_{γ}$ を有限集合とすると, $S \subset T_{β}$ なる $β < γ$ が存在する.よって, $T_{β}$ は有限充足可能であるから, $S$ は充足可能である.よって, $T_{γ}$ は有限充足可能である.以上より,すべての $α \leq ξ$ に対して, $T_{α}$ は有限充足可能であることが示された.

次に, $Σ = T_{ξ}$ とおく.このとき, 次は容易に確かめられる:

$T \subset Σ$ .
$Σ$ は有限充足可能である.
すべての $α < ξ$ に対して, $A_{α} \in Σ$ または $\neg A_{α} \in Σ$ であり,同時に成り立つことはない.

付値 $v$ を次のように定義する.
$v (p) = 1 ⟺ p \in Σ .$
この定義は前段の事実(3)からwell-definedである.このとき,
$v (A) = 1 ⟺ A \in Σ$
であることを論理式の構成に関する帰納法で容易に確かめられる.ゆえに, $v ⊨ Σ$ なので, $v ⊨ T$ である.従って, $T$ は充足可能である. $◻$

もし素論理式全体の集合 $PFml$ が可算であれば,論理式全体の集合 $F = Fml$ も可算であるから, $F$ は自然数全体の集合 $ω$ によって整列可能である.

Tychonoffの定理を用いた証明

最後に,もう1つの証明方法として位相空間論におけるTychonoffの定理を用いた証明を紹介します.証明はAraiを参考にしています.

まず, $I = PFml$ とおきます.このとき, $2^{I}$ とは,付値全体の集合のことです. $2 = {0, 1}$ に離散位相を入れて離散空間とみなすことで,直積空間 $2^{I}$ が考えられます.このとき, $2$ はコンパクトHausdorff空間であるから, Tychonoffの定理より, $2^{I}$ はコンパクトHausdorff空間であることがわかります.

このことから,有限交叉性を持つ $2^{I}$ の閉集合族 $F$ に対し, $⋂ F \neq \emptyset$ であることに注意します.ここで, $F$ が有限交叉性をもつとは, $F$ の任意の有限個の元の共通部分は常に空でないことをいいます.

$2^{I}$ の開基について,次の補題が成り立ちます.

$2^{I}$ の部分集合族 $B$ を次で定める.
$B = {B (s) ∣ I_{0} \subset I, | I_{0} | < ℵ_{0}, s : I_{0} \to 2}$
ここで, $I$ の有限部分集合 $I_{0}$ と関数 $s : I_{0} \to 2$ に対し, $B (s) = {v \in 2^{I} | s \subset v}$ である.このとき,次が成り立つ.

$B$ は $2^{I}$ の開基である.
$B (s) \in B$ は $2^{I}$ の開閉集合である.

(1)の証明

$U$ を $2^{I}$ の開集合, $v \in U$ とする.このとき, $2^{I}$ の位相の定義から,
$v \in ⋂_{i = 1}^{n} π_{P_{i}}^{- 1} (V_{i}) \subset U$
なる $P_{1}, \dots, P_{n} \in I$ と各 $i = 1, \dots, n$ に対して $2$ の開集合 $V_{i}$ がとれる.ここで, $π_{P_{i}} : 2^{I} \to 2$ は第 $P_{i}$ 座標への射影. $I_{0} = {P_{1}, \dots, P_{n}}$ とおき,関数 $s : I_{0} \to 2$ を $s (P_{i}) = π_{P_{i}} (v) = v (P_{i})$ で定める.このとき,
$v \in B (s) \subset ⋂_{i = 1}^{n} π_{P_{i}}^{- 1} (V_{i}) \subset U$
である.故に, $B$ は $2^{I}$ の開基である.

(2)の証明

$B (s)$ が $2^{I}$ の閉集合であることを示せばよい. $v \in 2^{I} ∖ B (s)$ とすると, $s ⊄ v$ なので, $s (Q) \neq v (Q)$ なる $Q \in I_{0}$ がとれる. $t : {Q} \to 2$ を $t (Q) = v (Q)$ で定めれば, $v \in B (t)$ であり, $u \in B (t)$ に対して $u (Q) = v (Q) \neq s (Q)$ なので, $u \notin B (s)$ である.故に, $2^{I} ∖ B (s)$ は $2^{I}$ の開集合なので, $B (s)$ は $2^{I}$ の閉集合である. $◻$

論理式 $A$ に対し,
$F_{A} = {v \in 2^{I} ∣ v ⊨ A}$
は $2^{I}$ の開閉集合である.

論理式の構成に関する帰納法で示す.

$A$ が素論理式のとき

前の補題で既に示されている.具体的には, $s : {P} \to 2$ を $s (P) = 1$ で定めるとき, $B (s) = F_{P}$ であるから,この $B (s)$ に前の補題を適用する.

論理式 $A, B$ に対して補題が成り立つとき

$F_{\neg A}, F_{A \cap B}, F_{A \cup B}, F_{A \to B}$ は $2^{I}$ の開閉集合であることを示そう.今,
$\begin{aligned} F_{\neg A} & = 2^{I} ∖ F_{A}, \\ F_{A \cap B} & = F_{A} \cap F_{B}, \\ F_{A \cup B} & = F_{A} \cup F_{B}, \\ F_{A \to B} & = (2^{I} ∖ F_{A}) \cup F_{B} \end{aligned}$
であるから,帰納法の仮定より示された. $◻$

$T$ を $I$ から生成される論理式全体の集合で,有限充足可能なものとする.このとき, $F = {F_{A} ∣ A \in T}$ とおくと, $⋂ F \neq \emptyset$ である.

前の補題より, $F$ は $2^{I}$ の開閉集合の族である.冒頭の注意より, $2^{I}$ はコンパクトなので, $F$ が有限交叉性をもつことを示せばよい.そこで,任意に $A_{1}, \dots, A_{n} \in T$ をとる.このとき, $I_{0} = {A_{1}, \dots, A_{n}} \subset T$ とおくと, $I_{0}$ は充足可能である.そこで, $v ⊨ I_{0}$ なる真理値割り当て $v$ をとる.よって,
$⋂_{i = 1}^{n} F_{A_{i}} \neq \emptyset$
である.

ここまでの準備を以って,コンパクト性定理を位相空間論の道具立てで証明します.

命題論理のコンパクト性定理(再掲)

論理式の集合 $T$ に対して,次は同値である.

$T$ は充足可能である.
$T$ は有限充足可能である.

$T$ は有限充足可能であるとする.前の補題より, $F = {F_{A} ∣ A \in T}$ について,
$⋂ F \neq \emptyset$
である.よって, $v \in ⋂ F$ がとれる.このとき, $A \in T$ に対して $v ⊨ A$ が成り立つので, $v ⊨ T$ である.故に, $T$ は充足可能である. $◻$

おわりに

今回は完全性定理,超限帰納法, Tychonoffの定理といった3つの方法を用いて命題論理のコンパクト性定理の証明をしました.多くの教科書は完全性定理の系としてコンパクト性定理を得ていますが,本稿では,完全性定理よりも実用的なコンパクト性定理に重きを置き,その証明を与えることにしました.特に2つ目の超限帰納法による証明では超限的議論を明確にし, Zornの補題やTukeyの補題のような,超限的議論をブラックボックス化することで整列集合の議論を避けて通る方法とは異なる証明の味わいがあると考えています.また, 3つ目のTychonoffの定理による証明は,コンパクト性定理という名と,位相空間論におけるコンパクト性との関連性を見出す重要な事実です.本稿が,なぜ超限帰納法が便利なのか,なぜ位相空間論が興味深いのかといった素朴な考えへの回答の一助になれば幸いです.