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

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

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

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

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

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

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

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

• (1)の証明

$ U $を$ 2^I $の開集合, $ v \in U $とする.このとき, $ 2^I $の位相の定義から,
$$ v \in \bigcap_{i=1}^{n} \pi_{P_i}^{-1}(V_i) \subset U $$
なる$ P_1, \cdots, P_n \in I $と各$ i = 1, \cdots, n $に対して$ 2 $の開集合$ V_i $がとれる.ここで, $ \pi_{P_i} \colon 2^I \to 2 $は第$ P_i $座標への射影. $ I_0 = \{ P_1, \cdots, P_n \} $とおき,関数$ s \colon I_0 \to 2 $を$ s(P_i) = \pi_{P_i}(v) = v(P_i) $で定める.このとき,
$$ v \in B(s) \subset \bigcap_{i=1}^{n} \pi_{P_i}^{-1}(V_i) \subset U $$
である.故に, $ \mathcal{B} $は$ 2^I $の開基である.

• (2)の証明

$ B(s) $が$ 2^I $の閉集合であることを示せばよい. $ v \in 2^I \setminus B(s) $とすると, $ s \not \subset v $なので, $ s(Q) \neq v(Q) $なる$ Q \in I_0 $がとれる. $ t \colon \{ 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 \setminus B(s) $は$ 2^I $の開集合なので, $ B(s) $は$ 2^I $の閉集合である. $\square$

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

• $A$が素論理式のとき

前の補題で既に示されている.具体的には, $ s \colon \{ 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 \rightarrow B} $は$ 2^I $の開閉集合であることを示そう.今,
\begin{align} F_{\neg A} &= 2^I \setminus F_A, \\ F_{A \cap B} &= F_A \cap F_B, \\ F_{A \cup B} &= F_A \cup F_B, \\ F_{A \rightarrow B} &= (2^I \setminus F_A) \cup F_B \\ \end{align}
であるから,帰納法の仮定より示された. $\square$

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

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