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

이번 글에서는 1차 논리에서의 건전성 정리에 대하여 설명할 것이다. 건전성이란, 명제논리를 다룰 때 설명했던 것과 같이, 구문론적 함의관계 $⊢$가 의미론적 함의관계 $\models$를 함의한다는 것이다. 즉, "$\mathrm{\Gamma }⊢\phi$이면, $\mathrm{\Gamma }\models \phi$이다"라는 성질을 건전성이라고 한다. 1차 논리에서의 건전성 정리란, 1차 논리는 건전하다는 정리이다. 그럼 바로 본론으로 들어가자.

 

Theorem 1. 1차 논리에서의 건전성 정리 ( Soundness Theorem for First Order Logic )

1차 논리 언어가 주어졌고, 주어진 언어의 wff의 집합 $\mathrm{\Gamma }$와 wff $\phi$가 주어졌을 때, $\mathrm{\Gamma }⊢\phi$가 성립한다면, $\mathrm{\Gamma }\models \phi$ 역시 성립한다.

 

Proof.

$\phi$에 대한 귀납법을 통해 증명하자.

만약, $\mathrm{\Gamma }⊢\phi$라면, wff $\phi$는 다음의 3가지로 분류할 수 있다.

1) $\phi \in \mathrm{\Gamma }$

2) $\phi$가 1차 논리의 공리이다.

3) $\phi$는 $\mathrm{\Gamma }⊢\psi$, $\mathrm{\Gamma }⊢\theta$를 만족하는 두 wff $\psi$, $\theta$에 MP를 적용한 결과이다.

이 중 1)의 경우는 $\mathrm{\Gamma }\models \phi$임이 자명하며, 3)의 경우 역시 귀납가정과 $\mathrm{\Gamma }\models \phi$의 정의에 의해 $\mathrm{\Gamma }\models \phi$임이 자명하다.

따라서 $\phi$가 1차 논리의 공리인 경우만 생각하면 충분하다.

 

먼저, (A1), (A2), (A3)에 대해 살펴보자.

${\models }_{\mathfrak{A}}\alpha [s]$일 때와 그렇지 않을 때, ${\models }_{\mathfrak{A}}\beta [s]$일 때와 그렇지 않을 때, ${\models }_{\mathfrak{A}}\alpha [s]$일 때와 그렇지 않을 때의 총 8가지 경우를 모두 따져 보면, 다음이 항상 성립한다는 것을 알 수 있다.

$$\begin{gathered} {\models }_{\mathfrak{A}}(\alpha \Rightarrow (\beta \Rightarrow \alpha ))[s] \\ {\models }_{\mathfrak{A}}((\alpha \Rightarrow (\beta \Rightarrow \gamma ))\Rightarrow ((\alpha \Rightarrow \beta )\Rightarrow (\alpha \Rightarrow \gamma )))[s] \\ {\models }_{\mathfrak{A}}((\left(\mathrm{\neg }\beta \right)\Rightarrow \left(\mathrm{\neg }\alpha \right))\Rightarrow ((\left(\mathrm{\neg }\beta \right)\Rightarrow \alpha )\Rightarrow \beta ))[s] \end{gathered}$$

따라서, $\phi$가 (A1), (A2), (A3) 중 하나인 경우에는 $\models \phi$가 성립하므로, $\mathrm{\Gamma }\models \phi$임은 자명하다.

 

이제 (Q1), (Q2), (Q3)에 대해 살펴보자.

 

먼저, $\phi$가 (Q1)의 꼴인 경우를 생각해보자.

즉, $\phi =(\mathrm{\forall }x\alpha \Rightarrow {\alpha }_t^x)$이고, $t$가 $\alpha$에서 $x$에 대해 substitutable하다고 하자.

이때, ${\models }_{\mathfrak{A}}\mathrm{\forall }x\alpha [s]$이면 ${\models }_{\mathfrak{A}}{\alpha }_t^x[s]$가 성립함을 증명하면, $\models \phi$인 것이 증명되므로, $\mathrm{\Gamma }\models \phi$가 자명한 귀결이 된다.

따라서 ${\models }_{\mathfrak{A}}\mathrm{\forall }x\alpha [s]$가 ${\models }_{\mathfrak{A}}{\alpha }_t^x[s]$를 함의함을 증명하면 충분하다.

이때, 만약 ${\models }_{\mathfrak{A}}{\alpha }_t^x[s]$인 것이 ${\models }_{\mathfrak{A}}\alpha [s(x|\overline{s}(t))]$인 것과 동치라면, ${\models }_{\mathfrak{A}}\mathrm{\forall }x\alpha [s]$가 ${\models }_{\mathfrak{A}}{\alpha }_t^x[s]$를 함의함은 자명하다. 왜냐하면, ${\models }_{\mathfrak{A}}\mathrm{\forall }x\alpha [s]$는 임의의 $d\in |\mathfrak{A}|$에 대하여 ${\models }_{\mathfrak{A}}\alpha [s(x|d)]$가 성립하는 것으로 정의되므로 ${\models }_{\mathfrak{A}}\alpha [s(x|\overline{s}(t))]$가 당연히 성립하게 될 것이기 때문이다.

이에 대해 논의하기에 앞서, term $u$, $t$, 변수 $x$에 대하여 $u$의 모든 $x$를 $t$로 치환한 term을 $u_t^x$라고 할 때, $\overline{s}(u_t^x)=\overline{s(x|\overline{s}(t))}(u)$임을 보이자.

이를 보이기 위해 $u$에 대한 귀납법을 사용할 것이다.

만약 $u$가 $x$가 아닌 변수라면, $u_t^x=u$이므로 위 등식은 $\overline{s}(u)=\overline{s}(u)$로 환원되므로 성립한다.

만약 $u=x$라면, $u_t^x=t$이므로 위 등식은 $\overline{s}(t)=\overline{s}(t)$로 환원되므로 성립한다.

만약 term $t_1,t_2,\cdots ,t_k$에 대하여 위 등식이 성립하고 $k$항 function symbol $f$에 대하여 $u=f{t}_1{t}_2\cdots t_k$라면, $u_t^x=f(t_1{)}_t^x(t_2{)}_t^x\cdots (t_k{)}_t^x$이므로 귀납가정에 의해 위 등식은 $f^{\mathfrak{A}}(\overline{s(x|\overline{s}(t))}(t_1),\overline{s(x|\overline{s}(t))}(t_2),\cdots ,\overline{s(x|\overline{s}(t))}(t_k))=f^{\mathfrak{A}}(\overline{s(x|\overline{s}(t))}(t_1),\overline{s(x|\overline{s}(t))}(t_2),\cdots ,\overline{s(x|\overline{s}(t))}(t_k))$로 환원되므로 성립한다.

즉, 모든 term $u$, $t$, 변수 $x$에 대하여 $\overline{s}(u_t^x)=\overline{s(x|\overline{s}(t))}(u)$이다.

이제 원래 논의로 돌아와서 ${\models }_{\mathfrak{A}}{\alpha }_t^x[s]$인 것과 ${\models }_{\mathfrak{A}}\alpha [s(x|\overline{s}(t))]$인 것이 동치임을 보이자.

이번엔 $\alpha$에 대한 귀납법을 통해 증명할 것이다.

먼저, $\alpha$가 원자명제인 경우를 생각하자. $\alpha$가 원자명제라면, 어떤 자연수 $k$가 존재하여, 어떤 $k$항 predicate symbol $P$에 대하여 $\alpha =P{u}_1{u}_2\cdots u_k$이다.

그런데, ${\models }_{\mathfrak{A}}{\alpha }_t^x[s]$인 것은 ${\models }_{\mathfrak{A}}P(u_1{)}_t^x(u_2{)}_t^x\cdots (u_k{)}_t^x[s]$인 것과 동치이고, 이는 곧 $(\overline{s}((u_1{)}_t^x),\overline{s}((u_2{)}_t^x),\cdots ,\overline{s}((u_k{)}_t^x))\in P^{\mathfrak{A}}$인 것과 동치이며, 이는 곧 $(\overline{s(x|\overline{s}(t))}(u_1),\overline{s(x|\overline{s}(t))}(u_2),\cdots ,\overline{s(x|\overline{s}(t))}(u_k))\in P^{\mathfrak{A}}$인 것과 동치이며, 이는 곧 ${\models }_{\mathfrak{A}}P{u}_1{u}_2\cdots u_k[s(x|\overline{s}(t))]$인 것과 동치이며, 이는 곧 ${\models }_{\mathfrak{A}}\alpha [s(x|\overline{s}(t))]$와 동치이므로, $\alpha$가 원자명제인 경우에는 ${\models }_{\mathfrak{A}}{\alpha }_t^x[s]$인 것과 ${\models }_{\mathfrak{A}}\alpha [s(x|\overline{s}(t))]$인 것이 동치이다.

 

이번엔 $\alpha$가 $\left(\mathrm{\neg }\beta \right)$꼴이거나 $(\beta \Rightarrow \gamma )$꼴인 경우를 생각하자. 이 경우에는 귀납가정에 의해 ${\models }_{\mathfrak{A}}{\alpha }_t^x[s]$인 것과 ${\models }_{\mathfrak{A}}\alpha [s(x|\overline{s}(t))]$인 것과 동치이다.

 

이번엔 $\alpha$가 $\mathrm{\forall }y\beta$이고 $x$가 $\alpha$의 자유변수가 아닌 경우를 생각하자. 이 경우에는 두 함수 $\overline{s}$와 $\overline{s(x|\overline{s}(t))}$의 $\alpha$의 자유변수에 대한 함숫값이 일치함이 자명하며, ${\alpha }_t^x$와 $\alpha$가 같은 wff가 되므로 ${\models }_{\mathfrak{A}}{\alpha }_t^x[s]$와 ${\models }_{\mathfrak{A}}\alpha [s(x|\overline{s}(t))]$는 동치이다.

 

이번엔 $\alpha$가 $\mathrm{\forall }y\beta$이고 $x$가 $\alpha$의 자유변수인 경우를 생각하자. 이 경우에는 $t$가 $\alpha$에서 $x$에 대해 substitutable하다는 조건으로부터 $y$가 $t$의 변수가 아니며 동시에 $t$가 $\beta$에서 $x$에 대해 substitutable하다는 사실을 알 수 있다.

따라서 임의의 $d\in |\mathfrak{A}|$에 대하여 $\overline{s}(t)=\overline{s(y|d)}(t)$가 성립함을 알 수 있다. $x$가 $\alpha$의 자유변수이므로 $x\ne y$임이 자명하며, 따라서 ${\alpha }_t^x=\mathrm{\forall }y{\beta }_t^x$임을 알 수 있다.

그러므로, ${\models }_{\mathfrak{A}}{\alpha }_t^x[s]$인 것은 임의의 $d\in |\mathfrak{A}|$에 대하여 ${\models }_{\mathfrak{A}}{\beta }_t^x[s(y|d)]$인 것과 동치이며, 이는 귀납가정과 $\overline{s}(t)=\overline{s(y|d)}(t)$라는 사실로부터 임의의 $d\in |\mathfrak{A}|$에 대하여 ${\models }_{\mathfrak{A}}\beta [s(y|d)(x|\overline{s}(t))]$인 것과 동치임을 알 수 있다. 이때, $x\ne y$이므로 임의의 $d\in |\mathfrak{A}|$에 대하여 ${\models }_{\mathfrak{A}}\beta [s(y|d)(x|\overline{s}(t))]$인 것은 ${\models }_{\mathfrak{A}}\mathrm{\forall }y\beta [s(x|\overline{s}(t))]$인 것과 동치이다. 따라서 ${\models }_{\mathfrak{A}}{\alpha }_t^x[s]$인 것은 ${\models }_{\mathfrak{A}}\alpha [s(x|\overline{s}(t))]$인 것과 동치이다.

 

따라서 귀납법에 의해 임의의 wff $\alpha$에 대하여 ${\models }_{\mathfrak{A}}{\alpha }_t^x[s]$인 것은 ${\models }_{\mathfrak{A}}\alpha [s(x|\overline{s}(t))]$인 것과 동치이다.

그러므로 $\phi$가 (Q1)꼴의 wff라면, $\models \phi$이므로 $\mathrm{\Gamma }\models \phi$가 성립한다.

 

이제 $\phi$가 (Q2)의 꼴인 경우를 생각해보자.

즉, $\phi =(\alpha \Rightarrow \mathrm{\forall }x\alpha )$이고 $x$가 $\alpha$의 자유변수가 아니라고 하자.

이때, ${\models }_{\mathfrak{A}}\alpha [s]$가 ${\models }_{\mathfrak{A}}\mathrm{\forall }x\alpha [s]$를 함의함을 증명한다면, $\models \phi$가 증명되며, 이로 인해 $\mathrm{\Gamma }\models \phi$는 자명한 귀결이 된다.

그런데, ${\models }_{\mathfrak{A}}\mathrm{\forall }x\alpha [s]$는 임의의 $d\in |\mathfrak{A}|$에 대하여 ${\models }_{\mathfrak{A}}\alpha [s(x|d)]$인 것과 동치이며, $x$가 $\alpha$의 자유변수가 아니므로 $\alpha$의 모든 자유변수에 대하여 $\overline{s}$와 $\overline{s(x|d)}$의 함숫값이 일치한다. 즉, ${\models }_{\mathfrak{A}}\alpha [s]$인 것과 ${\models }_{\mathfrak{A}}\alpha [s(x|d)]$인 것은 동치이다. 따라서 ${\models }_{\mathfrak{A}}\alpha [s]$인 것과 ${\models }_{\mathfrak{A}}\mathrm{\forall }x\alpha [s]$인 것이 동치임을 알 수 있으며, 이로 인해 $\phi$가 (Q2)꼴의 wff인 경우, $\mathrm{\Gamma }\models \phi$가 성립함을 알 수 있다.

 

이제 $\phi$가 (Q3)의 꼴인 경우를 생각해보자.

즉, $\phi =(\mathrm{\forall }x(\alpha \Rightarrow \beta )\Rightarrow (\mathrm{\forall }x\alpha \Rightarrow \mathrm{\forall }x\beta ))$라고 하자.

이때, ${\models }_{\mathfrak{A}}\mathrm{\forall }x(\alpha \Rightarrow \beta )[s]$가 ${\models }_{\mathfrak{A}}(\mathrm{\forall }x\alpha \Rightarrow \mathrm{\forall }x\beta )[s]$를 함의함을 증명한다면, $\models \phi$가 증명되며, 이로 인해 $\mathrm{\Gamma }\models \phi$는 자명한 귀결이 된다.

그런데, ${\models }_{\mathfrak{A}}\mathrm{\forall }x(\alpha \Rightarrow \beta )[s]$는 임의의 $d\in |\mathfrak{A}|$에 대하여 ${\models }_{\mathfrak{A}}(\alpha \Rightarrow \beta )[s(x|d)]$인 것과 동치이며, 이는 곧 임의의 $d\in |\mathfrak{A}|$에 대하여 ${⊭}_{\mathfrak{A}}\alpha [s(x|d)]$이거나 ${\models }_{\mathfrak{A}}\beta [s(x|d)]$인 것과 동치이다.

따라서 만약 임의의 $d\in |\mathfrak{A}|$에 대하여 ${\models }_{\mathfrak{A}}\alpha [s(x|d)]$라면, 자동적으로 임의의 $d\in |\mathfrak{A}|$에 대하여 ${\models }_{\mathfrak{A}}\beta [s(x|d)]$일 수밖에 없다. 동치인 다른 명제로 말하자면, ${\models }_{\mathfrak{A}}\mathrm{\forall }x\alpha [s]$가 ${\models }_{\mathfrak{A}}\mathrm{\forall }x\beta [s]$를 함의하게 된다. 따라서 ${\models }_{\mathfrak{A}}\mathrm{\forall }x(\alpha \Rightarrow \beta )[s]$는 ${\models }_{\mathfrak{A}}(\mathrm{\forall }x\alpha \Rightarrow \mathrm{\forall }x\beta )[s]$를 함의한다.

따라서 $\phi$가 (Q3) 꼴의 wff인 경우, $\models \phi$가 성립하며, 이로 인해 $\mathrm{\Gamma }\models \phi$ 역시 성립함을 알 수 있다.

 

이제 (E1), (E2)에 대해 살펴보자.

 

먼저, $\phi$가 (E1)의 꼴인 경우를 생각해보자.

즉, $\phi =(x=x)$라고 하자.

그런데, 임의의 구조 $\mathfrak{A}$와 임의의 함수 $s:V\to |\mathfrak{A}|$에 대하여, $\overline{s}(x)=\overline{s}(x)$임은 자명하므로 ${\models }_{\mathfrak{A}}=xx[s]$임은 자명하다.

따라서 $\models x=x[s]$이며, 이는 곧 $\mathrm{\Gamma }\models \phi$를 함의한다.

 

이제 $\phi$가 (E2)의 꼴인 경우를 생각해보자.

즉, $\phi =(x=y\Rightarrow (\alpha \Rightarrow {\alpha }^{\prime }))$이고 ${\alpha }^{\prime }$을 $\alpha$에 등장하는 $x$의 전부 또는 일부를 $y$로 치환한 wff라고 하자.

만약, ${\alpha }^{\prime }$이 $\alpha$라면, $\phi$는 공리 (A1), (A2)와 MP를 통해 얻을 수 있는 wff가 되므로 $\models \phi$임은 자명하다.

따라서 이제 수학적 귀납법에 의해 ${\alpha }^{\prime }$이 $\alpha$에 등장하는 $x$ 중 단 하나만을 $y$로 치환한 wff인 경우만 따져도 충분하다.

그런데, ${\models }_{\mathfrak{A}}x=y[s]$가 성립한다면, 임의의 자연수 $k$와 $k+1$항 function symbol $f$, $k$개의 term $t_1,t_2,\cdots ,t_k$에 대하여 $f^{\mathfrak{A}}(\overline{s}(x),\overline{s}(t_1),\overline{s}(t_2),\cdots ,\overline{s}(t_k))=f^{\mathfrak{A}}(\overline{s}(y),\overline{s}(t_1),\overline{s}(t_2),\cdots ,\overline{s}(t_k))$가 성립함은 자명하다.

따라서 귀납법에 의해 ${\alpha }^{\prime }$이 $\alpha$에 등장하는 $x$ 중 단 하나만을 $y$로 치환한 wff인 경우에는 ${\models }_{\mathfrak{A}}(x=y\Rightarrow (\alpha \Rightarrow {\alpha }^{\prime }))[s]$가 임의의 구조 $\mathfrak{A}$와 임의의 함수 $s:V\to |\mathfrak{A}|$에 대하여 성립한다.

즉, $\models (x=y\Rightarrow (\alpha \Rightarrow {\alpha }^{\prime }))$가 성립하며, 수학적 귀납법에 의해 $\models \phi$가 성립함을 알 수 있다.

따라서 $\phi$가 (E2) 꼴의 wff인 경우, $\mathrm{\Gamma }\models \phi$가 성립한다.

 

따라서 $\phi$가 공리일 때, $\mathrm{\Gamma }\models \phi$가 성립하며, 이로 인해 증명이 완성된다.

$◼$

 

건전성 정리에는 한 가지 매우 유명한 동치 명제가 존재한다. 해당 명제를 소개하기 전에 정의해야 할 것들이 있다. 다음 정의를 보자.

 

Definition 1. Satisfiability

1차 논리 언어가 주어졌고, 주어진 언어의 wff의 집합 $\mathrm{\Gamma }$가 주어졌다고 하자. 그러면 $\mathrm{\Gamma }$가 Satisfiable하다는 것은 어떤 구조 $\mathfrak{A}$와 어떤 함수 $s:V\to |\mathfrak{A}|$가 존재해서 $\mathrm{\Gamma }$의 모든 원소 $\phi$에 대하여 ${\models }_{\mathfrak{A}}\phi [s]$가 성립한다는 것을 말한다.

 

Definition 2. Consistency

1차 논리 언어가 주어졌고, 주어진 언어의 wff의 집합 $\mathrm{\Gamma }$가 주어졌다고 하자. 그러면 $\mathrm{\Gamma }$가 Consistent하다는 것은 $\mathrm{\Gamma }⊢\phi$이면서 동시에 $\mathrm{\Gamma }⊢\mathrm{\neg }\phi$인 wff $\phi$가 존재하지 않는다는 것을 말한다.

 

이제 건전성 정리의 동치 명제에 대해 알아보자. 다음 정리를 보라.

 

Theorem 2. 건전성 정리와 그의 동치 명제 ( Soundness Theorem and Its Equivalence )

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

 

Proof.

Part (a) -> (b)

귀류법을 이용한 증명을 하기 위해 (a)가 성립하고 $\mathrm{\Gamma }$가 satisfiable하지만, $\mathrm{\Gamma }⊢\phi$이고 $\mathrm{\Gamma }⊢\mathrm{\neg }\phi$인 wff $\phi$가 존재한다고 가정해보자.

$\mathrm{\Gamma }$가 satisfiable하므로 어떤 구조 $\mathfrak{A}$와 어떤 함수 $s:V\to |\mathfrak{A}|$가 존재하여 임의의 $\psi \in \mathrm{\Gamma }$에 대하여 ${\models }_{\mathfrak{A}}\psi [s]$가 성립한다.

그런데, $\mathrm{\Gamma }⊢\phi$라는 사실과 (a)로부터 $\mathrm{\Gamma }\models \phi$임을 알 수 있으므로 ${\models }_{\mathfrak{A}}\phi [s]$가 성립함을 알 수 있다.

또한, 같은 방식으로 ${\models }_{\mathfrak{A}}\mathrm{\neg }\phi [s]$ 역시 성립함을 알 수 있다.

그런데, ${\models }_{\mathfrak{A}}\mathrm{\neg }\phi [s]$인 것은 ${⊭}_{\mathfrak{A}}\phi [s]$인 것과 동치이므로 ${\models }_{\mathfrak{A}}\phi [s]$인 것과 모순이다.

따라서 (a)가 성립하면, (b)가 성립한다.

 

Part (b) -> (a)

귀류법을 이용한 증명을 하기 위해 (b)가 성립하고 $\mathrm{\Gamma }⊢\phi$가 성립하지만, $\mathrm{\Gamma }⊭\phi$라고 가정하자.

그러면 $\mathrm{\Gamma }⊢\phi$로부터 $\mathrm{\Gamma }\cup \{\mathrm{\neg }\phi \}$는 inconsistent함을 알 수 있다.

따라서 (b)에 의해 $\mathrm{\Gamma }\cup \{\mathrm{\neg }\phi \}$는 unsatisfiable하며, 이는 곧 임의의 구조 $\mathfrak{A}$, 함수 $s:V\to |\mathfrak{A}|$에 대하여 ${⊭}_{\mathfrak{A}}\mathrm{\neg }\phi [s]$이거나 어떤 $\psi \in \mathrm{\Gamma }$에 대해 ${⊭}_{\mathfrak{A}}\psi [s]$임을 의미한다.

이제 $\mathrm{\Gamma }⊭\phi$라는 사실에 주목해보자. 이는 곧 임의의 $\psi \in \mathrm{\Gamma }$에 대하여 ${\models }_{\mathfrak{A}}\psi [s]$가 성립하면서 동시에 ${⊭}_{\mathfrak{A}}\phi [s]$인 구조 $\mathfrak{A}$와 함수 $s$가 존재함을 의미한다.

그런데, 임의의 $\psi \in \mathrm{\Gamma }$에 대하여 ${\models }_{\mathfrak{A}}\psi [s]$가 성립하면, 위에서 보인 사실에 의해 ${⊭}_{\mathfrak{A}}\mathrm{\neg }\phi [s]$가 성립하며, 이는 ${\models }_{\mathfrak{A}}\phi [s]$와 동치이다. 따라서 임의의 $\psi \in \mathrm{\Gamma }$에 대하여 ${\models }_{\mathfrak{A}}\psi [s]$가 성립하면, ${\models }_{\mathfrak{A}}\phi [s]$가 성립함을 알 수 있으며, 이는 곧 정의에 의해 $\mathrm{\Gamma }\models \phi$가 성립함을 의미한다.

하지만, 이는 처음의 가정인 $\mathrm{\Gamma }⊭\phi$라는 사실과 모순이며, 이로 인해 (b)가 (a)를 함의함이 증명된다.

$◼$