논리학, 그 열여섯 번째 이야기 | 1차 논리에서의 완전성 정리 ( Completeness Theorem for First Order Logic )

이번 글에서는 1차 논리에서의 완전성 정리에 대하여 설명할 것이다. 완전성이란, 명제논리를 다룰 때 설명했듯이, 의미론적 함의 관계 $\models$가 구문론적 함의 관계 $⊢$를 함의한다는 것이다. 즉, "$\mathrm{\Gamma }\models \phi$이면 $\mathrm{\Gamma }⊢\phi$이다"라는 성질을 완전성이라고 한다. 1차 논리에서의 완전성 정리는 1차 논리는 완전하다는 정리이다. 1차 논리에서의 완전성 정리를 증명하기에 앞서, 그의 유명한 동치 명제에 대해 알아보도록 하자.

 

Theorem 1. Completeness Theorem and Its Equivalence

1차 논리 언어가 주어졌다고 하자. 그러면 다음 두 명제는 동치이다. (a) $\mathrm{\Gamma }\models \phi$이면 $\mathrm{\Gamma }⊢\phi$이다. (b) $\mathrm{\Gamma }$가 Consistent하면 $\mathrm{\Gamma }$는 Satisfiable하다.

 

Proof.

Part (a) -> (b)

귀류법을 이용한 증명을 하기 위해 (a)가 성립하고 $\mathrm{\Gamma }$가 consistent하지만, $\mathrm{\Gamma }$가 satisfiable하지 않다고 가정하자.

그러면 임의의 $\psi \in \mathrm{\Gamma }$에 대하여 ${\models }_{\mathfrak{A}}\psi [s]$가 성립하도록 하는 구조 $\mathfrak{A}$와 함수 $s:V\to |\mathfrak{A}|$가 존재하지 않으므로, 임의의 wff $\phi$에 대하여 $\mathrm{\Gamma }\models \phi$가 공허하게 참이다.

이때, (a)와 $\mathrm{\Gamma }\models \phi$로부터 $\mathrm{\Gamma }⊢\phi$를 얻을 수 있으며, 비슷하게 $\mathrm{\Gamma }⊢\mathrm{\neg }\phi$를 얻을 수 있다.

그런데, 이는 $\mathrm{\Gamma }$가 consistent하다는 가정에 모순이다.

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

 

Part (b) -> (a)

귀류법을 이용한 증명을 하기 위해 (b)가 성립하고 어떤 wff $\phi$에 대하여 $\mathrm{\Gamma }\models \phi$이지만 $\mathrm{\Gamma }⊬\phi$라고 가정하자.

여기서 $\mathrm{\Gamma }\models \phi$라는 사실에 주목하자.

$\mathrm{\Gamma }\models \phi$이므로 $\mathrm{\Gamma }\models (\phi \Rightarrow \phi )$가 성립함을 알 수 있으며, 따라서 $\mathrm{\Gamma }\models (\mathrm{\neg }\phi \Rightarrow \mathrm{\neg }\phi )$임을 알 수 있다.

이로 인해 $\mathrm{\Gamma }\cup \{\mathrm{\neg }\phi \}\models \mathrm{\neg }\phi$가 성립하며, $\mathrm{\Gamma }\models \phi$라는 사실을 함께 생각하면, 이는 곧 $\mathrm{\Gamma }\cup \{\mathrm{\neg }\phi \}$가 unsatisfiable함을 의미한다.

따라서 (b)에 의해 $\mathrm{\Gamma }\cup \{\mathrm{\neg }\phi \}$는 inconsistent하게 되고, 폭발 원리에 의해 $\mathrm{\Gamma }\cup \{\mathrm{\neg }\phi \}⊢\phi$임을 알 수 있다.

따라서 연역 정리에 의해 $\mathrm{\Gamma }⊢\mathrm{\neg }\phi \Rightarrow \phi$가 성립한다.

처음의 $\mathrm{\Gamma }⊬\phi$라는 가정과 배중률을 함께 적용하면, $\mathrm{\Gamma }⊢\mathrm{\neg }\phi$임을 알 수 있으며, 위에서 얻은 결론과 함께 MP를 적용한다면, $\mathrm{\Gamma }⊢\phi$를 얻을 수 있다.

이는 처음의 $\mathrm{\Gamma }⊬\phi$라는 가정에 모순이다.

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

$◼$

 

이번 글에서 동치명제를 먼저 소개한 데에는 이유가 있는데, 완전성 정리를 직접 증명하는 것보다는 그의 동치명제를 증명하는 것이 더 간단하기 때문이다. 그럼 다음 정리를 보자.

 

Theorem 2. 1차 논리에서의 완전성 정리 ( Completness Theorem for First Order Logic )

1차 논리 언어 $\mathcal{L}$이 주어졌다고 하자. $\mathcal{L}$의 wff의 집합 $\mathrm{\Gamma }$와 wff $\phi$가 주어질 때, $\mathrm{\Gamma }\models \phi$는 $\mathrm{\Gamma }⊢\phi$를 함의한다.

 

Proof.

Theorem 1에 의해 consistent하면 satisfiable하다는 것만 보여도 충분하다.

1차 논리 언어 $\mathcal{L}$과 $\mathcal{L}$의 wff의 집합 $\mathrm{\Gamma }$가 주어졌으며, $\mathrm{\Gamma }$가 consistent하다고 가정하자.

이 증명의 대략적인 개요를 설명하자면, 임의의 consistent한 $\mathrm{\Gamma }$를 maximal consistent set $\mathrm{\Delta }$로 확장 가능하다는 것을 보인 후, maximal consistent set $\mathrm{\Delta }$가 satisfiable하다는 것을 보이는 방식으로 정리를 증명할 것이다.

먼저, $\mathrm{\Gamma }$를 어떻게 확장할 수 있는지에 대해 논의해보자.

일단, $\mathcal{L}$의 기수가 무한기수 $\lambda$라고 하자. 즉, $\mathcal{L}$의 모든 변수의 집합의 기수가 $\lambda$라고 하자. 그러면 자명하게 $\mathcal{L}$의 모든 wff의 집합의 기수 역시 $\lambda$이다. 만약 $\mathcal{L}$의 변수의 집합이 유한집합이라면 가산개의 변수를 추가하여 변수의 집합이 가산무한집합이 되도록 하면 아래의 논의를 이어나갈 수 있다.

이제 $\mathcal{L}$의 constant symbol이 아닌 새로운 $\lambda$개의 constant symbol의 집합 $\mathbf{C}$를 생각하고, 이 새로운 constant symbol들을 포함하는 언어 ${\mathcal{L}}^{\prime }=\mathcal{L}\cup \mathbf{C}$를 생각하자. 이때, $\mathbf{C}$는 정렬된 집합으로 간주하자.

만약 $\mathrm{\Gamma }$가 ${\mathcal{L}}^{\prime }$에서는 inconsistent하다고 가정하면, $\mathrm{\Gamma }⊢\alpha$이면서 $\mathrm{\Gamma }⊢\mathrm{\neg }\alpha$인 ${\mathcal{L}}^{\prime }$의 wff $\alpha$가 존재한다.

그러면 Generalization on Constants에 의해 $\mathrm{\Gamma }⊢\mathrm{\neg }{\alpha }_y^c$이고 $\mathrm{\Gamma }⊢{\alpha }_y^c$이도록 하는 변수 $y$가 각 constant symbol $c$에 대하여 존재한다. 이때, $\alpha$에 등장하는 $\mathbf{C}$의 원소가 유한하므로 $\mathrm{\Gamma }⊢\mathrm{\neg }{\alpha }^{\prime }$이고 $\mathrm{\Gamma }⊢{\alpha }^{\prime }$이도록 하는 $\mathcal{L}$의 wff ${\alpha }^{\prime }$이 존재한다.

이는 $\mathrm{\Gamma }$가 consistent하다는 것에 모순이므로 $\mathrm{\Gamma }$는 ${\mathcal{L}}^{\prime }$에서도 consistent함을 알 수 있다.

이제 $\phi$가 ${\mathcal{L}}^{\prime }$의 wff이고 $x$가 변수인 순서쌍 $(\phi ,x)$의 $\lambda$-수열 $⟨({\phi }_i,x_i):i<\lambda ⟩$를 생각하자. 단, 이 수열에서 wff ${\phi }_i$는 중복되는 것이 없으며, 변수 $x_i$ 역시 중복되는 것이 없다. 또한, 모든 wff는 이 수열에서 적어도 한 번 등장하며, 모든 변수 역시 이 수열에서 적어도 한 번씩은 등장한다. 이러한 수열은 1차 논리 언어 ${\mathcal{L}}^{\prime }$의 기수가 $\lambda$이기 때문에 존재한다.

이제 ${\theta }_0$을 $\left(\mathrm{\neg }\mathrm{\forall }{x}_0{\phi }_0\right)\Rightarrow \left(\mathrm{\neg }{\phi }_0{}_{c_0}^{x_0}\right)$로 정의하자. 이때, $c_0$은 ${\phi }_0$에 등장하지 않는 $\mathbf{C}$의 원소 중 첫 번째 원소로 정의된다.

이제 $0$이 아닌 순서수 $\xi <\lambda$에 대하여 ${\theta }_{\xi }$를 $\left(\mathrm{\neg }\mathrm{\forall }{x}_{\xi }{\phi }_{\xi }\right)\Rightarrow \left(\mathrm{\neg }{\phi }_{\xi }{}_{c_{\xi }}^{x_{\xi }}\right)$로 정의하자. 이때, $c_{\xi }$는 ${\phi }_{\xi }$와 $\gamma <\xi$인 ${\theta }_{\gamma }$에 등장하지 않는 $\mathbf{C}$의 원소 중 첫 번째 원소로 정의된다.

또한, $\mathrm{\Theta }=\{{\theta }_{\xi }|\xi <\lambda \}$, ${\mathrm{\Theta }}_{\xi }=\{{\theta }_{\gamma }|\gamma \le \xi \}$라고 하자.

만약 $\mathrm{\Gamma }\cup \mathrm{\Theta }$가 inconsistent하다면, 연역과정이 유한하다는 사실로부터 $\mathrm{\Gamma }\cup {\mathrm{\Theta }}_{\xi }$가 inconsistent한 $xi$가 존재한다.

그러한 $\xi$ 중 최솟값을 생각하자.

만약 $\xi =0$이면, 귀류법에 의해 $\mathrm{\Gamma }⊢\mathrm{\neg }{\theta }_0$이다.

그러면 공리꼴 (A1), (A2), (A3)에 의해 $\mathrm{\Gamma }⊢\mathrm{\neg }\mathrm{\forall }{x}_0{\phi }_0$이며 $\mathrm{\Gamma }⊢{\phi }_0{}_{c_0}^{x_0}$임을 알 수 있다.

그런데, $c_0$가 $Gamma$나 ${\phi }_0$에서 등장하지 않으므로 Generalization on Constants의 따름정리에 의해 $\mathrm{\Gamma }⊢{\phi }_0{}_{c_0}^{x_0}$으로부터 $\mathrm{\Gamma }⊢\mathrm{\forall }{x}_0{\phi }_0$임을 알 수 있으며, 이는 $\mathrm{\Gamma }$의 consistency에 모순이다.

만약 $\xi$가 따름 서수라면, $\xi =\gamma +1$인 $\gamma$를 선택하자.

만약 $\xi$가 $0$이 아닌 극한 서수라면, 연역과정은 유한하다는 사실로부터 고정된 wff $\beta$에 대하여 ${\theta }_{\gamma }$가 $\mathrm{\Gamma }\cup {\mathrm{\Theta }}_{\xi }$로부터 $\beta$ 또는 $\mathrm{\neg }\beta$로의 연역과정에 등장하는 $\gamma <\xi$ 중 가장 큰 순서수를 $\gamma$로 선택하자.

그러면, $\mathrm{\Gamma }\cup {\mathrm{\Theta }}_{\gamma }\cup \{{\theta }_{\xi }\}$는 inconsistent함을 알 수 있다.

이때, 귀류법에 의해 $\mathrm{\Gamma }\cup {\mathrm{\Theta }}_{\gamma }⊢\mathrm{\neg }{\theta }_{\xi }$가 성립하며, 공리꼴 (A1), (A2), (A3)에 의해 $\mathrm{\Gamma }⊢\mathrm{\neg }\mathrm{\forall }{x}_{\xi }{\phi }_{x}i$이며 $\mathrm{\Gamma }⊢{\phi }_{\xi }{}_{c_{\xi }}^{x_{\xi }}$임을 알 수 있다.

$c_{\xi }$가 $\mathrm{\Gamma }\cup {\mathrm{\Theta }}_{\gamma }$나 ${\phi }_{\xi }$에서 등장하지 않으므로 Generalizatoin on Constants의 따름정리에 의해 $\mathrm{\Gamma }⊢{\phi }_{\xi }{}_{c_{\xi }}^{x_{\xi }}$로부터 $\mathrm{\Gamma }⊢\mathrm{\forall }{x}_{\xi }{\phi }_{\xi }$를 얻을 수 있으며, 이는 $\mathrm{\Gamma }\cup {\mathrm{\Theta }}_{\gamma }$가 inconsistent함을 의미한다.

하지만, $\gamma <\xi$이며, $\xi$가 $\mathrm{\Gamma }\cup {\mathrm{\Theta }}_{\xi }$가 inconsistent한 최소의 서수이므로 $\mathrm{\Gamma }\cup {\mathrm{\Theta }}_{\gamma }$가 inconsistent한 것은 모순이다.

따라서 $\mathrm{\Gamma }\cup \mathrm{\Theta }$는 consistent하다.

이제 maximal consistent set $\mathrm{\Delta }$를 구성할 차례이다.

먼저, $\mathrm{\Gamma }\cup \mathrm{\Theta }\cup \{{\phi }_0\}$가 consistent하다면, 이것을 ${\mathrm{\Delta }}_0$으로 정의하고, 그렇지 않다면, ${\mathrm{\Delta }}_0=\mathrm{\Gamma }\cup \mathrm{\Theta }\cup \{\mathrm{\neg }{\phi }_0\}$이라고 하자.

또한, $0$이 아닌 서수 $\xi$에 대하여 ${\displaystyle \bigcup _{\gamma <\xi }{\mathrm{\Delta }}_{\gamma }\cup \{{\phi }_{\xi }\}}$가 consistent하다면, 이것을 ${\mathrm{\Delta }}_{\xi }$로 정의하고, 그렇지 않다면, ${\mathrm{\Delta }}_{\xi }={\displaystyle \bigcup _{\gamma <\xi }{\mathrm{\Delta }}_{\gamma }\cup \{\mathrm{\neg }{\phi }_{\xi }\}}$라고 하자.

그리고 $\mathrm{\Delta }={\displaystyle \bigcup _{\xi <\lambda }{\mathrm{\Delta }}_{\xi }}$로 정의하자.

만약 $\mathrm{\Gamma }\cup \mathrm{\Theta }\cup \{{\phi }_0\}$이 inconsistent하다면, 귀류법에 의해 $\mathrm{\Gamma }\cup \mathrm{\Theta }⊢\mathrm{\neg }{\phi }_0$이다. 이때, $\mathrm{\Gamma }\cup \mathrm{\Theta }$가 consistent하다는 것을 이미 위에서 보였으므로 $\mathrm{\Gamma }\cup \mathrm{\Theta }\cup \{\mathrm{\neg }{\phi }_0\}$이 consistent하게 된다. 따라서 ${\mathrm{\Delta }}_0$은 consistent하다.

이제 임의의 $\gamma <\xi$에 대하여 ${\mathrm{\Delta }}_{\gamma }$가 consistent하다고 가정하고 ${\displaystyle \bigcup _{\gamma <\xi }{\mathrm{\Delta }}_{\gamma }\cup \{{\phi }_{\xi }\}}$가 inconsistent하다고 가정하자.

그러면 귀류법에 의해 ${\displaystyle \bigcup _{\gamma <\xi }{\mathrm{\Delta }}_{\gamma }⊢\mathrm{\neg }{\phi }_{\xi }}$가 성립한다. 따라서 ${\displaystyle \bigcup _{\gamma <\xi }{\mathrm{\Delta }}_{\gamma }}$가 consistent하다면, ${\mathrm{\Delta }}_{\xi }$ 역시 consistent함을 알 수 있다.

만약 ${\displaystyle \bigcup _{\gamma <\xi }{\mathrm{\Delta }}_{\gamma }}$가 inconsistent하다면, 연역과정이 유한하므로, 고정된 wff $\beta$에 대하여 $\beta$ 또는 $\mathrm{\neg }\beta$의 ${\displaystyle \bigcup _{\gamma <\xi }{\mathrm{\Delta }}_{\gamma }}$의 연역과정에서 등장하는 모든 $\psi \in {\displaystyle \bigcup _{\gamma <\xi }{\mathrm{\Delta }}_{\gamma }}$에 대하여 $\psi \in {\mathrm{\Delta }}_{\gamma }$가 성립하도록 하는 $\gamma$의 최댓값이 존재한다.

이는 곧 ${\mathrm{\Delta }}_{\gamma }⊢\beta$이면서 ${\mathrm{\Delta }}_{\gamma }⊢\mathrm{\neg }\beta$임을 의미하며, 이는 귀납가정에 모순이다.

 따라서 ${\displaystyle \bigcup _{\gamma <\xi }{\mathrm{\Delta }}_{\gamma }}$는 consistent하며, 이로 인해 ${\mathrm{\Delta }}_{\xi }$ 역시 consistent하다.

비슷한 논리로, $\mathrm{\Delta }$ 역시 consistent함을 알 수 있다.

또한, 이후의 논의에서 $\mathrm{\Delta }$의 중요한 성질이 사용될 것이므로 해당 성질을 미리 증명하자.

만약 $\phi \in \mathrm{\Delta }$라면, $\mathrm{\Delta }⊢\phi$임은 자명하다.

만약 $\mathrm{\Delta }⊢\phi$이면, $\mathrm{\Delta }$가 consistent하므로 $\mathrm{\Delta }⊬\mathrm{\neg }\phi$이다.

따라서 $\mathrm{\neg }\phi \notin \mathrm{\Delta }$임을 알 수 있으며, 따라서 $\phi \in \mathrm{\Delta }$이다.

이제 $\mathrm{\Delta }$가 satisfiable하다는 것을 보이면 증명이 끝난다.

그러기 위해 $\mathrm{\Delta }$를 이용하여 ${\mathcal{L}}^{\prime }$에서 등호 $=$을 $2$항 predicate symbol $E$로 대체한 언어의 구조 $\mathfrak{A}$를 구성할 것이다. 다음을 만족하는 구조 $\mathfrak{A}$를 생각하자.

(a) $\mathfrak{A}$의 universe $|\mathfrak{A}|$는 ${\mathcal{L}}^{\prime }$의 모든 term의 집합이다.

(b) 두 term $u$, $t$에 대하여 $(u,t)\in E^{\mathfrak{A}}$인 것은 $(u=t)\in \mathrm{\Delta }$인 것과 동치이다.

(c) 각 $n$항 predicate symbol $P$에 대하여 $P^{\mathfrak{A}}$는 다음과 같이 정의된다.

$(t_1,t_2,\cdots ,t_n)\in P^{\mathfrak{A}}$인 것은 $P{t}_1{t}_2\cdots t_n\in \mathrm{\Delta }$인 것과 동치이다.

(d) 각 $n$항 function symbol $f$에 대하여 함수 $f^{\mathfrak{A}}$는 다음과 같이 정의된다.

$$f^{\mathfrak{A}}(t_1,t_2,\cdots ,t_n)=f{t}_1{t}_2\cdots t_n$$

또한, 함수 $s:V\to |\mathfrak{A}|$는 $s:x\mapsto x$로 정의하자.

그러면 임의의 term $t$에 대하여 $\overline{s}(t)=t$임을 귀납법을 통해 쉽게 알 수 있다.

 

이제 $E^{\mathfrak{A}}$가 동치관계임을 보이자.

먼저, $x{E}^{\mathfrak{A}}x$는 $x=x\in \mathrm{\Delta }$인 것과 동치이고, 이는 $\mathrm{\Delta }$의 성질에 의해 $\mathrm{\Delta }⊢x=x$와 동치이다. 그런데, $⊢x=x$이므로 $\mathrm{\Delta }⊢x=x$가 성립함은 자명하며, 따라서 $x{E}^{\mathfrak{A}}x$이다. 즉, $E^{\mathfrak{A}}$는 반사적이다.

이번엔 $E^{\mathfrak{A}}$가 대칭적이라는 것을 확인하자.

$x{E}^{\mathfrak{A}}y$를 가정하면, $x=y\in \mathrm{\Delta }$임을 알 수 있으며, $x=y⊢y=x$이므로 $x=y\in \mathrm{\Delta }$는 $\mathrm{\Delta }⊢y=x$를 함의한다. 또한, 이는 $\mathrm{\Delta }$의 성질에 의해 $\mathrm{\Delta }⊢y=x$와 동치이며, 이는 $y{E}^{\mathfrak{A}}x$와 동치이다.

이번엔 $E^{\mathfrak{A}}$가 추이적이라는 것을 확인하자.

$x{E}^{\mathfrak{A}}y$와 $y{E}^{\mathfrak{A}}z$를 가정하면, $x=y,y=z\in \mathrm{\Delta }$임을 알 수 있으며, $x=y,y=z⊢x=z$이므로 $\mathrm{\Delta }⊢x=z$임을 알 수 있다. 또한, 이는 $\mathrm{\Delta }$의 성질에 의해 $x=z\in \mathrm{\Delta }$와 동치이며, 이는 곧 $x{E}^{\mathfrak{A}}z$임을 의미한다.

따라서 $E^{\mathfrak{A}}$는 동치관계이다.

사실, $E^{\mathfrak{A}}$는 동치관계일 뿐 아니라 $\mathfrak{A}$에서의 합동관계이다. 즉, 다음을 모두 만족한다.

(a) $E^{\mathfrak{A}}$는 $|\mathfrak{A}|$ 위의 동치관계이다.

(b) 각 $n$항 predicate symbol $P$에 대하여 다음이 성립한다.

$(t_1,t_2,\cdots ,t_n)\in P^{\mathfrak{A}}$이고 동시에 각 $1\le i\le n$에 대하여 $t_i{E}^{\mathfrak{A}}{t}_i^{\prime }$이면 $(t_1^{\prime },t_2^{\prime },\cdots ,t_n^{\prime })\in P^{\mathfrak{A}}$이다.

(c) 각 $n$항 function symbol $f$에 대하여 다음이 성립한다.

각 $1\le i\le n$에 대하여 $t_i{E}^{\mathfrak{A}}{t}_i^{\prime }$이면 $f^{\mathfrak{A}}(t_1,t_2,\cdots ,t_n)E^{\mathfrak{A}}{f}^{\mathfrak{A}}(t_1^{\prime },t_2^{\prime },\cdots ,t_n^{\prime })$이다.

(a)가 성립함은 이미 위에서 보였으니 (b)와 (c)만 보여도 충분하며, (b)와 (c)가 성립함은 공리꼴 (E2)에 의해 자명하다.

따라서 몫구조 $\mathfrak{A}/E$를 다음과 같이 정의할 수 있다.

몫구조 $\mathfrak{A}/E$는 다음을 만족하는 구조이다.

(a) $|\mathfrak{A}/E|=|\mathfrak{A}|/E^{\mathfrak{A}}$이다. 이에 대해서는 동치류와 몫집합을 참고하라.

(b) 각 $n$항 predicate symbol $P$에 대하여 다음이 성립한다.

$(\left[t_1\right],\left[t_2\right],\cdots ,\left[t_n\right])\in P^{\mathfrak{A}/E}$는 $(t_1,t_2,\cdots ,t_n)\in P^{\mathfrak{A}}$와 동치이다.

(c) 각 $n$항 function symbol $f$에 대하여 다음이 성립한다.

$f^{\mathfrak{A}/E}(\left[t_1\right],\left[t_2\right],\cdots ,\left[t_n\right])=\left[f^{\mathfrak{A}}(t_1,t_2,\cdots ,t_n)\right]$

또한, 함수 $s:V\to |\mathfrak{A}/E|$를 $s:x\mapsto \left[x\right]$로 정의하자. 그러면 임의의 term $t$에 대하여 $\overline{s}(t)=\left[t\right]$가 성립함은 자명하다.

이제 이렇게 정의된 구조 $\mathfrak{A}/E$에 대하여 $\phi \in \mathrm{\Delta }$와 ${\models }_{\mathfrak{A}/E}\phi [s]$가 동치임을 보이면, $\mathrm{\Delta }$가 satisfiable하다는 것이 보여지게 된다.

$\phi \in \mathrm{\Delta }$와 ${\models }_{\mathfrak{A}/E}\phi [s]$가 동치임을 보이기 위해 귀납법을 사용하자. 즉, 다음의 5가지 경우에 대해 살펴보자.

(i) $\phi$가 원자명제인 경우

(ii) $\phi =\left(\mathrm{\neg }\varphi \right)$인 경우

(iii) $\phi =(\varphi \Rightarrow \psi )$인 경우

(iv) $\phi =\mathrm{\forall }x\varphi$인 경우

 

먼저, (i)의 경우를 살펴보자.

$\phi$가 $t=t^{\prime }$ 꼴의 wff인 경우, 다음의 과정에 따라 주장이 성립한다.

$$\begin{array}{lll}\phi \in \mathrm{\Delta }& \text{iff}& t{E}^{\mathfrak{A}}{t}^{\prime }\\ & \text{iff}& [t]=[t^{\prime }]\\ & \text{iff}& \overline{s}(t)=\overline{s}(t^{\prime })\\ & \text{iff}& {\models }_{\mathfrak{A}/E}t=t^{\prime }[s]\end{array}$$

\varphi$가$Pt_1t_2\cdots t_n$꼴의 wff인 경우, 다음의 과정에 따라 주장이 성립한다.

$$\begin{array}{lll}\phi \in \mathrm{\Delta }& \text{iff}& (t_1,t_2,\cdots ,t_n)\in P^{\mathfrak{A}}\\ & \text{iff}& (\left[t_1\right],\left[t_2\right],\cdots ,\left[t_n\right])\in P^{\mathfrak{A}/E}\\ & \text{iff}& {\models }_{\mathfrak{A}/E}P{t}_1{t}_2\cdots t_n[s]\end{array}$$

 

이제 (ii)의 경우를 살펴보자.

$\phi$가 $neg\varphi$ 꼴의 wff인 경우, 다음의 과정에 따라 주장이 성립한다.

$$\begin{array}{lll}\phi \in \mathrm{\Delta }& \text{iff}& \varphi \notin \mathrm{\Delta }\\ & \text{iff}& {⊭}_{\mathfrak{A}/E}\varphi [s]\\ & \text{iff}& {\models }_{\mathfrak{A}/E}\phi [s]\end{array}$$

 

이제 (iii)의 경우를 살펴보자.

$\phi$가 $\varphi \Rightarrow \psi$ 꼴의 wff인 경우, 다음의 과정에 따라 주장이 성립한다.

$$\begin{array}{lll}\phi \in \mathrm{\Delta }& \text{iff}& \mathrm{\Delta }⊢\phi \\ & \text{iff}& \mathrm{\neg }\varphi \in \mathrm{\Delta }\text{ or }\psi \in \mathrm{\Delta }\\ & \text{iff}& {\models }_{\mathfrak{A}/E}\mathrm{\neg }\varphi [s]\text{ or }{\models }_{\mathfrak{A}/E}\psi [s]\\ & \text{iff}& {\models }_{\mathfrak{A}/E}\phi [s]\end{array}$$

 

이제 (iv)의 경우를 살펴보자.

이번에는 right-side와 left-side를 나눠서 증명할 것이다.

먼저 right-side를 생각해보자.

$$\begin{array}{lllll}{⊭}_{\mathfrak{A}/E}\mathrm{\forall }x\varphi [s]& \text{if only}& {⊭}_{\mathfrak{A}/E}\varphi [s(x|[t])]& \text{for some }t\in |\mathfrak{A}|& \\ & \text{if only}& {⊭}_{\mathfrak{A}/E}\psi [s(x|[t])]& \text{by }\text{Alphabetic Variants}\text{ \& }\text{Soundness Theorem}\\ & \text{if only}& {⊭}_{\mathfrak{A}/E}{\psi }_t^x[s]& \text{by substitution}\\ & \text{if only}& {\psi }_t^x\notin \mathrm{\Delta }& \text{by inductive hypothesis}\\ & \text{if only}& \mathrm{\forall }x\psi \notin \mathrm{\Delta }& \\ & \text{if only}& \mathrm{\forall }x\varphi \notin \mathrm{\Delta }& \text{by Alphabetic Variants \& Soundness Theorem}\end{array}$$

이 과정에서 Alphabetic Variants를 사용하여 서술을 우회한 것은 만약 이와 같이 우회하지 않고 논리를 전개하는 경우에는 $t$가 $\varphi$에서 $x$에 대해 substitutable한 경우에만 성립하는 반쪽자리 증명이 되기 때문이다.

이제 left-side를 생각하자.

$$\begin{array}{llll}{\models }_{\mathfrak{A}/E}\mathrm{\forall }x\varphi [s]& \text{if only}& {\models }_{\mathfrak{A}/E}\varphi [s(x|[c])]& \text{for some constant symbol }c\in |\mathfrak{A}|\\ & \text{if only}& {\models }_{\mathfrak{A}/E}{\varphi }_c^x[s]& \text{by substitution}\\ & \text{if only}& {\varphi }_c^x\in \mathrm{\Delta }& \text{by induction hypothesis}\\ & \text{if only}& \mathrm{\forall }x\varphi \in \mathrm{\Delta }& \text{since there exists a constant symbol}\\ & & & c\text{ such that }\left(\mathrm{\neg }\mathrm{\forall }x\varphi \right)\Rightarrow \left(\mathrm{\neg }{\varphi }_c^x\right)\in \mathrm{\Delta }\end{array}$$

따라서 귀납법에 의해 $\phi \in \mathrm{\Delta }$와 ${\models }_{\mathfrak{A}/E}\phi [s]$가 동치임이 증명된다.

즉, $\mathrm{\Delta }$는 ${\mathcal{L}}^{\prime }$에서 satisfiable하다.

따라서 $\mathrm{\Gamma }\subseteq \mathrm{\Delta }$ 역시 ${\mathcal{L}}^{\prime }$에서 satisfiable함을 알 수 있다.

또한, ${\mathcal{L}}^{\prime }$에서 $\mathcal{L}$로의 자연스러운 축소를 통해 $\mathrm{\Gamma }$가 $\mathcal{L}$에서도 satisfiable함을 알 수 있다.

따라서 완전성 정리가 증명된다.

$◼$