건전성과 완전성

이 강좌의 체계에 관한 두 질문

연역에 관한 단원은 이 강좌의 체계를 정했다. 우카시에비치의 공리 도식 A1, A2, A3와 두 규칙, 곧 전건 긍정식(MP)과 이중 부정 대체(RDN)이며, 후자는 네 가지 연역 기법 수업이 이중 부정을 증명한 뒤에 더한 것이다. 집합 $\Gamma$에서의 연역은 논리식의 유한한 열로서, 그 각 논리식은 공리이거나, $\Gamma$의 원소이거나, 앞선 두 논리식에 전건 긍정식을 적용한 결과이거나, 앞선 한 논리식에 이중 부정 대체를 적용한 결과이다. 그리고 $\Gamma \vdash \varphi$는 $\Gamma$에서의 연역으로서 마지막 논리식이 $\varphi$인 것이 존재한다는 뜻이다. 의미론에 관한 단원은 의미론적 귀결과 동치 수업에서 관계 $\Gamma \models \varphi$를 정의했다. 곧 $\Gamma$의 모든 논리식을 충족하는 모든 진리값 할당은 $\varphi$도 충족한다. 두 관계는 같은 모양으로 쓰여, 왼쪽에는 집합, 오른쪽에는 논리식이 온다. 그러나 그 성격은 정반대이다. 앞의 것은 구문론적이고 존재적이다. 그것은 유한한 어떤 것, 곧 연역이 존재하며 그것을 기호 하나하나 검토할 수 있다고 주장한다. 뒤의 것은 의미론적이고 전칭적이다. 그것은 모든 진리값 할당에 대해 무언가를 주장하는데, 할당은 무한히 많고 그 각각은 무한히 많은 변항에 값을 준다.

그러므로 체계에 대해 두 질문이 생긴다. 첫째, 체계는 연역해야 할 것만 연역하는가? 모든 집합 $\Gamma$와 모든 논리식 $\varphi$에 대해 $\Gamma \vdash \varphi$가 $\Gamma \models \varphi$를 함축하면, 체계가 건전하다고 한다. 전제로부터 연역되는 것은 전제를 참으로 만드는 모든 할당 아래에서 참이다. 둘째, 체계는 연역해야 할 것을 모두 연역하는가? $\Gamma \models \varphi$가 $\Gamma \vdash \varphi$를 함축하면, 체계가 완전하다고 한다. 완전성에는 어떤 전제 집합을 다루느냐에 따라 세 단계가 있다.

• 약한 완전성: $\models \varphi$이면 $\vdash \varphi$이다. 모든 항진식은 정리이다.
• 유한 전제 집합의 완전성: $\{\gamma_{1}, \ldots, \gamma_{k}\} \models \varphi$이면 $\{\gamma_{1}, \ldots, \gamma_{k}\} \vdash \varphi$이다.
• 강한 완전성: $\Gamma \models \varphi$이면 $\Gamma \vdash \varphi$이다. 여기서 집합 $\Gamma$는 임의의 집합이며, 무한해도 된다.

이 수업은 건전성과 완전성의 처음 두 단계를 증명한다. 셋째 단계는 콤팩트성 정리 수업에서 증명하며, 왜 이렇게 나누는지는 이 수업의 끝에서 설명한다.

말하지 말아야 할 것

스페인어에서는 건전성을 때때로 “solvencia”라고 부르는데, 이것은 영어 soundness를 그대로 옮긴 말이다. 스페인어 용어는 “corrección”이고, 이 강좌의 한국어 용어는 “건전성”이다. 또한 건전성을 체계가 “표현의 집합에서 하나의 표현을 추론하는” 성질로 정의해서도 안 된다. 그것은 연역 가능성 자체이지 체계의 성질이 아니다. 그러나 본질적인 오류는 다른 두 가지이다.

첫째는 건전성과 완전성이 “서로에게서 추론될 수 있다”고 말하는 것이다. 둘은 독립된 성질이다. 이중 부정 대체 규칙이 없는 우카시에비치의 체계는 건전하지만(이 수업의 증명에서 경우 하나를 빼면 그것이 증명된다) 완전하지 않다(형식 연역 체계 수업은 이 체계가 연역하지 못하는 항진식을 보였다). 그리고 모든 논리식을 공리로 삼는 체계는 완전하지만 건전하지 않다. 예제 2에서 두 예를 살펴본다.

둘째 오류는 더 심각하다. 순환 논증을 완전성의 증명으로 내놓기 때문이다. 그 요지는 이렇다. $\varphi \nvdash \psi$이면, 연역 정리에 의해 $\nvdash (\varphi \rightarrow \psi)$이다. “건전성에 의해” $\not\models (\varphi \rightarrow \psi)$이다. 의미론적 연역 정리에 의해 $\varphi \not\models \psi$이다. 그런데 건전성이 말하는 것은 연역 가능한 것은 타당하다는 것이고, 그 대우가 말하는 것은 타당하지 않은 것은 연역 가능하지 않다는 것이다.

논증의 그 단계는 반대 방향, 곧 $\nvdash \chi$에서 $\not\models \chi$로 나아가며, 이것은 $\models \chi \Rightarrow \vdash \chi$의 대우, 곧 약한 완전성이다. 그렇다면 이 논증은 증명하려는 것을 전제한다. 그러므로 완전성은 “간단한 방식으로 추론되는” 것이 아니다. 그것은 이 강좌에서 가장 깊은 결과이며, 그 증명이 이 수업의 대부분을 차지한다. 끝으로, 완전성을 “참인 모든 표현에는 증명이 있다”고 요약하는 것은 부정확하다. 증명을 가지는 것은 타당한 논리식, 곧 모든 할당 아래에서 참인 것이지, 어떤 할당 아래에서 참인 것이 아니다. 변항 $v_{1}$은 많은 할당 아래에서 참이지만 정리가 아니다.