논리학, 그 아홉 번째 이야기 | 명제논리에서의 콤팩트성 정리 ( Compactness Theorem for Propositional Logic )

이번 글에서는 명제논리에서의 콤팩트성 정리를 증명할 것이다. 콤팩트성 정리에 대해 설명하기 위해 꼭 필요한 개념이 있는데, 바로 만족가능성 (Satisfiability)이다. 만족가능성이란, 쉽게 말해서 wff의 집합의 모든 원소가 동시에 참이 될 수 있는가이다. 엄밀하게는 다음과 같이 정의한다.

 

Definition 1.

wff의 집합 $\Sigma$의 모든 원소를 만족하는 Boolean Interpretation $v$가 존재할 때, $\Sigma$가 Satisfiable하다고 한다.

 

그리고 콤팩트성 정리의 서술의 편의를 위해 다음의 개념을 추가로 정의하자.

 

Definition 2.

wff의 집합 $\Sigma$의 모든 유한 부분집합이 satisfiable하다면, $\Sigma$가 Finitely Satisfiable하다고 한다.

 

이제 satisfiable이 무엇인지 알았으니 콤팩트성 정리의 증명에 사용될 보조정리 하나를 보자.

 

Lemma 1.

wff의 집합 $\Sigma$가 finitely satisfiable하다고 하자. 그러면 임의의 wff $\alpha$에 대하여 $\Sigma \cup \{ \alpha \}$와 $\Sigma \cup \{ \neg \alpha \}$ 둘 중 적어도 하나는 finitely satisfiable하다.

 

Proof.

$\Sigma \cup \{ \alpha \}$와 $\Sigma \cup \{ \neg \alpha \}$ 둘 모두가 finitely unsatisfiable하다고 하자. 그러면 $\Sigma$의 두 유한 부분집합 $\Sigma_1$과 $\Sigma_2$가 존재해서 $\Sigma_1 \cup \{ \alpha \}$와 $\Sigma_2 \cup \{ \neg \alpha \}$가 unsatisfiable하다.

$\bar{\Sigma} = \Sigma_1 \cup \Sigma_2$라고 하면 $\bar{\Sigma}$는 $\Sigma$의 유한 부분집합이므로 satisfiable하다. 이때 $\Sigma_1 \cup \{ \alpha \}$가 unsatisfiable하므로 $\bar{\Sigma} \cup \{ \alpha \}$ 역시 unsatisfiable하다. 즉, $\bar{\Sigma}$를 만족시키는 모든 boolean interpretation $v$에 대하여 $\bar{v}(\alpha) \neq \mathbf{T}$이다. 또한, $\Sigma_2 \cup \{ \neg \alpha \}$도 unsatisfiable하므로 $\bar{\Sigma} \cup \{ \neg \alpha \}$ 역시 unsatisfiable하다. 즉, $\bar{\Sigma}$를 만족시키는 모든 boolean interpretaion $v$에 대하여 $\bar{v}(\neg \alpha) \neq \mathbf{T}$이다. 하지만 $\bar{v}$의 정의에 의해 $\bar{v}(\alpha)$와 $\bar{v}(\neg \alpha)$ 중 하나는 $\mathbf{T}$이어야 하므로 $\bar{v}(\alpha) \neq \mathbf{T}$, $\bar{v}(\neg\alpha) \neq \mathbf{T}$는 모순이다. 따라서 $\Sigma \cup \{ \alpha \}$와 $\Sigma \cup \{ \neg \alpha \}$가 동시에 finitely unsatisfiable할 수는 없다.

$\blacksquare$

 

Theorem 1. 명제논리에서의 콤팩트성 정리 ( Compactness Theorem for Propositional Logic )

wff의 집합 $\Sigma$에 대하여 다음이 성립한다: $\Sigma$가 satisfiable한 것과 $\Sigma$가 finitely satisfiable한 것은 동치이다.

 

Proof.

먼저, $\Sigma$가 satisfiable하다면 $\Sigma$의 모든 원소를 만족하는 boolean interpretation $v$가 존재한다. 이때, $\Sigma$의 임의의 유한 부분집합 $\sigma$에 대하여 $\sigma$의 원소는 항상 $\Sigma$의 원소이므로 $v$가 $\sigma$의 모든 원소를 만족한다. 따라서 $\sigma$는 satisfiable하며, $\sigma$의 선택이 임의적이었으므로 $\Sigma$는 finitely satisfiable하다.

이제 $\Sigma$가 finitely satisfiable하면 $\Sigma$가 satisfiable하다는 것을 증명하자. 먼저, $\Sigma$가 유한집합이라면 $\Sigma$ 자신이 $\Sigma$의 유한 부분집합이 되므로 $\Sigma$가 finitely satisfiable하다면 $\Sigma$ 역시 satisfiable하다. 따라서 $\Sigma$가 무한집합인 경우만 다뤄도 충분하다. 이제 $\Sigma$가 무한집합임을 가정하자.

명제논리의 모든 wff의 집합은 가산집합이다. 따라서 모든 wff를 원소로 가지는 수열 $\{ \alpha_n \}_{n \in \mathbb{N}}$이 존재한다. 자세한 내용은 정렬정리를 참고하라. 이를 이용하여 wff의 집합의 열 $\{ \Delta_n \}_{n \in \mathbb{N}}$을 다음과 같이 귀납적으로 정의하자.

 

$\Delta_0 = \Sigma$
만약 $\Delta_n \cup \{ \alpha_{n+1} \}$이 finitely satisfiable하면 $\Delta_{n+1} = \Delta_n \cup \{ \alpha_{n+1} \}$. 그렇지 않은 경우에는 $\Delta_{n+1} = \Delta_n \cup \{ \neg \alpha_{n+1} \}$.

 

그러면 Lemma 1에 의하여 $\Delta_n$은 언제나 finitely satisfiable하다.

$\Delta = \displaystyle \bigcup_{n=1}^{\infty} \Delta_n$이라고 하자. 그러면 $\Sigma \subseteq \Delta$이며, 임의의 wff $\alpha$에 대하여 $\alpha \in \Delta$ 또는 $\left( \neg \alpha \right) \in \Delta$이다. 또한, $\Delta$의 임의의 유한 부분집합은 어떤 자연수 $n$에 대하여 $\Delta_n$의 유한 부분집합이므로 $\Delta$ 역시 finitely satisfiable하다.

이제 boolean interpretation $v$를 다음과 같이 정의하자.

원자명제 $A$가 $\Delta$의 원소인 경우 $v(A) = \mathbf{T}$, 그렇지 않은 경우엔 $v(A) = \mathbf{F}$.

그러면 $v$가 wff $\varphi$를 만족하는 것과 $\varphi$가 $\Delta$의 원소인 것이 동치이다. 이에 대한 증명은 아래 "증명 보기"를 클릭하면 볼 수 있다.

 

$v \models \varphi$와 $\varphi \in \Delta$가 동치라는 것을 보이기 위해 $\phi$의 길이에 대한 수학적 귀납법을 사용할 것이다.

먼저, $\phi$의 길이가 1인 경우, $\phi$는 원자명제가 되므로 $v$의 정의에 의해 $v \models \varphi$와 $\varphi \in \Delta$가 동치이다.

이제 길이가 $n$ 이하인 모든 wff에 대하여 $v$가 해당 wff를 만족하는 것과 해당 wff가 $\Delta$의 원소인 것이 동치라고 가정하고 $\phi$의 길이가 $n+1$이라고 하자. 그러면 $\phi = \neg \alpha$인 wff $\alpha$가 존재하는 경우와 $\phi = \alpha_1 \Rightarrow \alpha_2$인 wff $\alpha_1$, $\alpha_2$가 존재하는 경우로 나눠서 생각할 수 있다.

 

Case 1. $\phi = \neg \alpha$

이 경우, $\alpha$의 길이가 $n$이므로 귀납가정에 의해 $v \models \alpha$와 $\alpha \in \Delta$는 동치이다. 

만약 $v \models \phi$라면 자명하게 $\bar{v}(\alpha) = \mathbf{F}$이다. 따라서 $\alpha \notin \Delta$이며, $\alpha$와 $\neg \alpha$ 둘 중 하나는 $\Delta$의 원소이므로 $\phi = \neg \alpha$는 $\Delta$의 원소이다.

만약 $\phi \in \Delta$라면 $\alpha \notin \Delta$이며, 그 이유는 다음과 같다.

$\alpha \in \Delta$라면 $\{ \alpha, \neg \alpha \} \subseteq \Delta$이고, $\Delta$가 finitely satisfiable하므로 $\{ \alpha, \neg \alpha \}$는 satisfiable해야 한다. 하지만 이는 자명하게 모순이며, 따라서 $\alpha \in \Delta$일 수 없다.

따라서 $\bar{v}(\alpha) = \mathbf{F}$가 되고, $\phi$는 $\alpha$의 부정이므로 $\bar{v}(\phi) = \mathbf{T}$이다. 따라서 $v \models \phi$이다.

 

Case 2. $\phi = \alpha_1 \Rightarrow \alpha_2$

이 경우, $\alpha_1$과 $\alpha_2$의 길이의 합이 $n$이므로 귀납가정에 의해 $v \models \alpha_1$과 $\alpha_1 \in \Delta$는 동치이며, $v \models \alpha_2$와 $\alpha_2 \in \Delta$는 동치이다.

만약 $v \models \phi$라면 자명하게 $\bar{v}(\alpha_1) = \mathbf{F}$이거나 $\bar{v}(\alpha_2) = \mathbf{T}$이다. 따라서 $\alpha_1 \notin \Delta$이거나 $\alpha_2 \in \Delta$이다. 이때, $\alpha_1$과 $\neg \alpha_1$ 중 적어도 하나는 $\Delta$의 원소이므로 $\neg \alpha_1$과 $\alpha_2$ 중 적어도 하나는 $\Delta$의 원소가 된다. 만약 $\neg \alpha_1 \in \Delta$라면 $\Delta$가 finitely satisfiable하다는 사실로부터 자명하게 $\neg \left( \alpha_1 \Rightarrow \alpha_2 \right) \notin \Delta$이다. 따라서 $\alpha_1 \Rightarrow \alpha_2 \in \Delta$이다. 또한, 만약 $\alpha_2 \in \Delta$라면 이때 역시 $\Delta$가 finitely satisfiable하다는 사실로부터 자명하게 $\neg \left( \alpha_1 \Rightarrow \alpha_2 \right) \notin \Delta$이다. 따라서 $\alpha_1 \Rightarrow \alpha_2 \in \Delta$이다. 즉, $v \models \phi$라면 $\phi \in \Delta$이다.

만약 $\phi \in \Delta$라면 자명하게 $\neg \alpha_1 \in \Delta$이거나 $\alpha_2 \in \Delta$이다. 그 이유는 $\alpha_1 \in \Delta$이고 $\neg \alpha_2 \in \Delta$라면 $\{ \phi, \alpha_1, \neg \alpha_2 \}$가 satisfiable해야 하고 이는 모순이기 때문이다. 따라서 $v \models \neg \alpha_1$이거나 $v \models \alpha_2$이며, $\bar{v}$의 정의에 의해 자명하게 $v \models \alpha_1 \Rightarrow \alpha_2$이다. 즉, $\phi \in \Delta$라면 $v \models \phi$이다.

 

따라서 $\phi \in \Delta$와 $v \models \phi$는 동치이며, 수학적 귀납법에 의해 이는 모든 wff $\phi$에 대하여 성립한다.

$\blacksquare$

 

위 사실에 의해 $\Sigma \subseteq \Delta$로부터 위에서 정의한 boolean interpretation $v$가 $\Sigma$의 모든 원소를 만족한다. 따라서 $\Sigma$는 satisfiable하다.

$\blacksquare$

 

위의 정리로부터 아래의 따름정리를 얻을 수 있다.

 

Corollary 1.

wff의 집합 $\Sigma$와 wff $\mathscr{C}$에 대하여 $\Sigma \models \mathscr{C}$이면 $\Sigma_0 \models \mathscr{C}$인 유한집합 $\Sigma_0 \subseteq \Sigma$가 존재한다.

 

Proof.

따름정리를 증명하기 위해 한 가지 사실을 받아들이자. $\Sigma \models \mathscr{C}$는 $\Sigma \cup \{ \neg \mathscr{C} \}$가 unsatisfiable한 것과 동치이다. 이에 대한 증명은 아래 "증명 보기"를 클릭하면 볼 수 있다.

 

먼저, $\Sigma \models \mathscr{C}$라면 $\bar{v}\left( \Sigma \right) = \{ \mathbf{T} \}$인 모든 boolean interpretation $v$에 대하여 $\bar{v}\left( \mathscr{C} \right) = \mathscr{T}$이다. 따라서 $\bar{v} \left( \neg \mathscr{C} \right) = \mathscr{F}$이고, 이로 인해 $\Sigma \cup \{ \neg \mathscr{C} \}$는 unsatisfiable하다.

이제 $\Sigma \cup \{ \neg \mathscr{C} \}$가 unsatisfiable하다고 하자. 그러면 $\bar{v} \left( \Sigma \right) = \{ \mathbf{T} \}$이고 $\bar{v} \left( \neg \mathscr{C} \right) = \mathbf{T}$인 boolean interpretation $v$는 존재하지 않는다. 따라서 $\bar{v} \left( \Sigma \right) = \{ \mathbf{T} \}$이면 $\bar{v} \left( \neg \mathscr{C} \right) = \mathbf{F}$이며, 이로 인해 $\bar{v} \left( \mathscr{C} \right) = \mathbf{T}$이다. 따라서 $\Sigma \models \mathscr{C}$이다.

$\blacksquare$

 

귀류법을 통해 따름정리를 증명할 것이다. 먼저 따름정리가 거짓이라고 가정하자.

그러면 $\Sigma \models \mathscr{C}$이면서 임의의 유한집합 $\Sigma_0 \subseteq \Sigma$에 대하여 $\Sigma_0 \models \mathscr{C}$가 거짓이 되도록 하는 $\Sigma$와 $\mathscr{C}$가 존재한다. 이때, $\Sigma_0 \models \mathscr{C}$가 아니므로 $\Sigma_0 \cup \{ \neg \mathscr{C} \}$는 satisfiable하다. 따라서 모든 유한집합 $\Sigma_0 \subseteq \Sigma$가 satisfiable하며, 따라서 $\Sigma$는 finitely satisfiable하다.

이제 유한집합 $\bar{\Sigma} \subseteq \Sigma \cup \{ \neg \mathscr{C} \}$를 생각하자.

만약 $\neg \mathscr{C} \notin \bar{\Sigma}$라면 $\bar{\Sigma}$가 $\Sigma$의 유한 부분집합이므로 $\bar{\Sigma}$는 satisfiable하다. 만약 $\neg \mathscr{C} \in \bar{\Sigma}$라면 $\bar{\Sigma} = \Sigma_i \cup \{ \neg \mathscr{C} \}$인 유한집합 $\Sigma_i \subseteq \Sigma$가 존재한다. 따라서 위에서 증명한 사실에 의해 $\bar{\Sigma}$는 satisfiable하다.

따라서 $\Sigma \cup \{ \neg \mathscr{C} \}$은 finitely satisfiable하며, Theroem 1에 의해 $\Sigma \cup \{ \neg \mathscr{C} \}$는 satisfiable하다. 하지만, $\Sigma \models \mathscr{C}$는 $\Sigma \cup \{ \neg \mathscr{C} \}$가 unsatisfiable한 것과 동치이므로 모순이 발생한다. 따라서 따름정리는 거짓이 될 수 없으며, 결국 따름정리가 증명된다.

$\blacksquare$

 

놀랍게도 Theorem 1과 Corollary 1은 동치이다. 아래 정리를 보자.

 

Theorem 2.

Theorem 1과 Corollary 1은 동치이다.

 

Proof.

Theorem 1이 Corollary 1을 함의함은 위에서 이미 증명했으므로 Corollary 1이 Theorem 1을 함의함을 증명하면 정리가 증명된다.

또한, satisfiable하면 finitely satisfiable한 것은 자명하며 finitely satisfiable한 유한집합이 satisfiable한 것은 자명하므로 finitely satisfiable한 무한집합이 satisfiable한 것만 보여도 충분하다.

이제 정리가 거짓이라고 가정하자. 즉, Corollary 1은 참이고 unsatisfiable하면서 동시에 finitely satisfiable한 무한집합 $\Sigma$가 존재한다고 가정하자.

$\mathscr{B} \in \Sigma$라고 하자. 이때, $\bar{\Sigma}$를 $\bar{\Sigma} = \Sigma \cup \{ \neg \neg \mathscr{B} \}$로 정의하자. 그러면 $\bar{\Sigma} \models \neg \neg \mathscr{B}$임은 당연하다. 그러면 Corollary 1에 의해 $\Sigma_0 \models \neg \neg \mathscr{B}$인 유한집합 $\Sigma_0 \subseteq \bar{\Sigma}$가 존재한다.

이제 $\bar{\Sigma}$가 finitely satisfiable하며 동시에 unsatisfiable하다는 것을 확인하자. 이에 대한 증명은 아래의 "증명 보기"를 클릭하면 볼 수 있다.

 

먼저, $\bar{\Sigma}$가 unsatisfiable하다는 것은 $\bar{\Sigma}$의 부분집합인 $\Sigma$가 unsatisfiable하므로 자명하다.

$\bar{\Sigma}$의 유한 부분집합 $\Sigma'$를 생각하자. 만약 $\neg \neg \mathscr{B} \notin \Sigma'$이라면 $\Sigma'$은 $\Sigma$의 유한 부분집합이므로 satisfiable하다. 만약 $\neg \neg \mathscr{B} \in \Sigma'$이라면 $\Sigma' = \Sigma_i \cup \{ \neg \neg \mathscr{B} \}$인 $\Sigma$의 유한 부분집합 $\Sigma_i$가 존재한다. 그러면 $\Sigma_i \cup \{ \mathscr{B} \}$ 역시 $\Sigma$의 유한 부분집합이며, 따라서 $\Sigma_i \cup \{ \mathscr{B} \}$는 satisfiable하다. 이때, 임의의 boolean interpretation $v$에 대하여 $\bar{v} \left( \neg \neg \mathscr{B} \right) = \bar{v} \left( \mathscr{B} \right)$이므로 $\Sigma_i \cup \{ \neg \neg \mathscr{B} \}$ 역시 satisfiable하다. 즉, $\bar{\Sigma}$의 유한 부분집합 $\Sigma'$은 항상 satisfiable하다.

따라서 $\bar{\Sigma}$는 finitely satisfiable하다.

$\blacksquare$

 

그러면 $\Sigma \cup \{ \neg \neg \mathscr{B} \}$가 unsatisfiable하므로 $\Sigma \models \neg \mathscr{B}$이다. 이에 대한 증명은 Corollary 1의 증명과정을 참고하라. 그러면 Corollary 1에 의해 $\Sigma_0 \models \neg \mathscr{B}$인 유한집합 $\Sigma_0 \subseteq \Sigma$가 존재한다. 그러면 $\Sigma_0 \cup \{ \neg \neg \mathscr{B} \} \subseteq \bar{\Sigma}$이고 $\bar{\Sigma}$가 finitely satisfiable하므로 $\Sigma_0 \cup \{ \neg \neg \mathscr{B} \}$는 satisfiable하다.

그러면 $\Sigma_0 \models \neg \mathscr{B}$로부터 $\bar{v} \left( \Sigma_0 \right) = \{ \mathbf{T} \}$인 모든 boolean interpretation $v$에 대하여 $\bar{v} \left( \neg \mathscr{B} \right) = \mathbf{T}$이다. 하지만, $\Sigma_0 \cup \{ \neg \neg \mathscr{B} \}$가 satisfiable하다는 사실로부터 $\bar{v} \left( \Sigma_0 \cup \{ \neg \neg \mathscr{B} \} \right) = \{ \mathbf{T} \}$인 boolean interpretation $v$가 존재하며, 이는 모순을 이끌어낸다.

따라서 Corollary 1은 Theorem 1을 함의하며, 이로 인해 둘은 동치임이 증명된다.

$\blacksquare$