논리학, 그 열일곱 번째 이야기 | 1차 논리에서의 콤팩트성 정리 ( Compactness Theorem for First Order Logic )

이번 글에서는 1차 논리에서의 콤팩트성 정리에 대하여 설명할 것이다. 콤팩트성이란, 명제논리를 다룰 때 설명했듯이, finitely satisfiable하면 satisfiable하다는 것이다. 즉, "모든 유한부분집합이 satisfiable하다면, 그 자신도 satisfiable하다"는 성질을 콤팩트성이라고 한다. 1차 논리에서의 콤팩트성 정리는 1차 논리는 콤팩트하다는 정리이다. 아래를 보자.

 

Theorem 1. 1차 논리에서의 콤팩트성 정리 ( Compactness Theorem for First Order Logic )

1차 논리 언어 $\mathcal{L}$이 주어졌다고 하자. $\mathcal{L}$의 wff의 집합 $\Gamma$에 대하여, $\Gamma$가 finitely satisfiable하면 $\Gamma$도 satisfiable하다. 단, 어떤 집합 $\Gamma$가 finitely satisfiable하다는 것은, $\Gamma$의 모든 유한 부분집합이 satisfiable하다는 것을 의미한다.

 

Proof.

귀류법을 이용한 증명을 위해 정리가 거짓이라고 가정하자.

그러면 finitely satisfiable하면서 동시에 unsatisfiable한 wff의 집합 $\Gamma$가 존재한다.

$\Gamma$가 unsatisfiable하므로 완전성 정리에 의해 $\Gamma \vdash \varphi$이고 동시에 $\Gamma \vdash \neg \varphi$이도록 하는 wff $\varphi$가 존재한다.

이제 $\left< \alpha_1, \alpha_2, \cdots, \alpha_n \right>$를 $\Gamma$로부터 $\varphi$로의 연역 과정이라고 하자.

그러면 유한집합 $\Gamma_1 = \{ \alpha_i \;|\; \alpha_i \in \Gamma \}$를 생각할 수 있으며, $\left< \alpha_1, \alpha_2, \cdots, \alpha_n \right>$가 $\Gamma$로부터 $\varphi$로의 연역 과정이므로 매우 자명하게 $\left< \alpha_1, \alpha_2, \cdots, \alpha_n \right>$가 $\Gamma_1$로부터 $\varphi$로의 연역 과정임을 알 수 있다.

즉, $\Gamma_1 \vdash \varphi$가 성립한다.

같은 방법을 통해 $\Gamma_2 \vdash \neg \varphi$인 유한집합 $\Gamma_2 \subseteq \Gamma$가 존재함을 알 수 있다.

이제 $\Gamma_0 = \Gamma_1 \cup \Gamma_2$를 생각하자.

그러면 $\Gamma_0 \vdash \varphi$이고 동시에 $\Gamma_0 \vdash \neg \varphi$임을 알 수 있으며, $\Gamma_0 \subseteq \Gamma$는 유한집합임을 알 수 있다.

따라서 $\Gamma$의 어떤 유한 부분집합이 inconsistent함을 알 수 있으며, 이는 완전성 정리에 의해 $\Gamma$의 어떤 유한 부분집합이 unsatisfiable하다는 것을 함의하고, 이는 $\Gamma$가 finitely satisfiable하다는 것에 모순이다.

따라서 $\Gamma$는 satisfiable하며, 이로 인해 정리가 증명된다.

$\blacksquare$

 

콤팩트성 정리에는 아주 유명한 동치명제가 있다. 사실, 일반적으로는 위의 Theorem 1과 그의 동치명제 모두 콤팩트성 정리라고 부르며, 딱히 구분하지 않는다. 다음 정리를 보자.

 

Theorem 2. Compactness Theorem and Its Equivalence

1차 논리 언어 $\mathcal{L}$이 주어질 때, 다음 두 명제는 동치이다. (a) $\mathcal{L}$의 wff의 집합 $\Gamma$가 finitely satisfiable하면 $\Gamma$는 satisfiable하다. (b) $\mathcal{L}$의 wff의 집합 $\Gamma$와 wff $\varphi$에 대하여 $\Gamma \models \varphi$가 성립한다면, $\Gamma_0 \models \varphi$가 성립하도록 하는 유한집합 $\Gamma_0 \subseteq \Gamma$가 존재한다.

 

Proof.

Part (a) -> (b)

(a)가 성립함을 가정하고, (b)의 대우명제가 성립함을 증명하자.

$\Gamma$의 모든 유한 부분집합 $\Gamma_0$에 대하여 $\Gamma_0 \not \models \varphi$임을 가정하자.

이때, $\Gamma \cup \{ \neg \varphi \}$가 unsatisfiable한 것과 $\Gamma \models \varphi$인 것이 동치이므로, $\Gamma$의 모든 유한 부분집합 $\Gamma_0$에 대하여 $\Gamma_0 \cup \{ \neg \varphi \}$가 satisfiable하다.

따라서 (a)에 의해 $\Gamma \cup \{ \neg \varphi \}$가 satisfiable하며, 따라서 $\Gamma \not \models \varphi$임을 알 수 있다.

 

Part (b) -> (a)

귀류법을 이용한 증명을 위해 (b)가 성립함을 가정하고, (a)가 성립하지 않는다고 가정하자.

그러면 finitely satisfiable하지만 satisfiable하지는 않은 wff의 집합 $\Gamma$가 존재한다.

따라서 건전성 정리에 의해 $\Gamma \models \varphi$이고 $\Gamma \models \neg \varphi$인 wff $\varphi$가 존재한다.

그러면 (b)에 의해 $\Gamma_0 \models \varphi$이고 $\Gamma_1 \models \varphi$이도록 하는 유한집합 $\Gamma_0, \Gamma_1 \subseteq \Gamma$이 존재한다.

따라서 $\overline{\Gamma} = \Gamma_0 \cup \Gamma_1$에 대하여 $\overline{\Gamma} \models \varphi$와 $\overline{\Gamma} \models \varphi$가 동시에 성립하며, 완전성 정리에 의해 $\overline{\Gamma}$는 unsatisfiable하다.

그러나, $\overline{\Gamma}$는 $\Gamma$의 유한 부분집합이므로 $\overline{\Gamma}$가 unsatisfiable한 것은 $\Gamma$의 finitely satisfiability에 모순이다.

따라서 (b)는 (a)를 함의한다.

$\blacksquare$