술어논리(9) ㅡ 추론, 건전성, 완전성

 논리학의 추론규칙체계는 다양합니다. 공리체계, 자연연역체계, 시퀀트체계가 대표적으로 많이 쓰이고 트리체계나 다른 여러 방식이 쓰이기도 합니다. 모두 소개하기엔 체계들도 많고 그에 대한 변형도 존재하고, 또한 하나를 소개하는 것도 제대로 설명하려면 상당히 복잡하기 때문에 현재로서는 어떤 추론체계를 설명하지는 않겠습니다. 나중에 시간이 되면 자연연역 같은 체계를 간단히 소개해 볼 것입니다. 여기서는 어느 체계에서나 통용되는 개념적으로 중요한 사실에 대해서만 언급하겠습니다.

 항상 아래와 같은 건 아니지만 보통 아래와 같이 증명가능성을 정의할 수 있습니다. 공리란 자명한 것으로 받아들여지는 문장이나 그것들의 집합을 뜻합니다. 이를 사용하여 '증명가능성' '도출가능성'을 아래와 같이 정의할 수 있습니다. 자연연역이나 다른 방식에서는 공리가 아에 없는 경우도 있기 때문에, 아래에서 공리라는 단어가 체계에 따라 빠질 수 있습니다. 

$\Gamma$는 문장들의 집합, $\alpha$는 문장일 때

$\Gamma\vdash\alpha$는

1. $\Gamma$의 문장들에 (특정 추론체계에서 받아들여지는) 추론규칙을 적용하여 $\alpha$를 얻을 수 있다'는 의미이다.

1'. 좀더 정확히는 어떤 문장들의 열, $<\alpha_1, \alpha_2, ..., \alpha_n>$이 있어서 $\alpha_1$는 공리이거나 $\Gamma$의 원소이고, 임의의 $i\leq n$에 대해 $\alpha_i$는 공리이거나, $\Gamma$의 원소이거나, $i$열보다 앞선 문장들에 의해 추론규칙을 사용하여 얻어져야 하고, 결과로 도출되는 $\alpha_n$은 $\alpha$이어야 한다.

 $\Gamma\vdash\alpha$는 $\alpha$는 $\Gamma$로부터 증명가능하다, 도출가능하다고 말합니다. 혹은, $\alpha$는 $\Gamma$의 정리(theorem)라고 합니다. 수학에서 정리라고 하는 말이 이 말입니다. 현대 수학은 $\in$이라는 원소기호와 몇 가지 수학적 공리들을 사용해서 얻어지는데 $\Gamma$를 수학공리들의 집합이라고 하고 수학의 언어가 논리상항 + $\in$라고 생각한다면 우리가 말하는 수학의 정리는 모두 $\Gamma$로부터 증명가능한 문장들이고 따라서 일반적으로 $\Gamma\vdash\alpha$에서 $\alpha$를 $\Gamma$의 정리라고 부르는 데에 큰 문제가 없을 겁니다.

 이와 대비해서 메타정리라는 게 있습니다. 메타정리는 논리학 자체에 대한 결과입니다. 즉, $\Gamma\vdash\alpha$ 형태로 나타나는 문장들이 아니라 논리학의 기호에 대한 정의들에 대해 생산해낼 수 있는 결과물입니다. 앞에서 만족가능성과 논리적 함축 개념이 서로 상호교환가능하다는 것도, 우리가 다루는 술어논리학 자체가 가지는 성질에 관한 것입니다. 이와 관련하여 매우 중요한 정리가 논리학에 대한 건전성과 완전성 정리입니다.

 건전성 정리(soundness theorem)는 $\Gamma\vdash\alpha\Longrightarrow\Gamma\models\alpha$입니다. 말하자면, $\Gamma$에서 증명가능한 문장은, $\Gamma$에서 참입니다. 달리 말하면, 추론규칙을 포함한 추론체계에서 생산되는 문장들이 진리라는 개념을 보존한다고 보시면 됩니다. 어떤 논리학의 체계가 이런 성질을 만족할 때, 논리학의 체계가 건전하다고 말합니다. 다시 말해 공리와 추론규칙으로 삼은 것들이 진리(참)의 관점에서 문제가 없다는 것이고, 추론체계는 항상 참을 생산해내기 때문에 건전한 체계라는 것이죠.

 만약 건전하지 않은 체계라면 그 논리학의 체계는 쓸모가 없을 겁니다. 추론규칙을 통해서 얻어낸 문장이 진리를 보존하지 않는다면(즉 참이 아니라면) 아무리 좋은 결과를 추론해낸다해도 거짓이 될 수 있으므로 불안정한 체계일 수밖에 없겠죠. 그런 체계는 누구도 가지고 싶지 않을 겁니다.

 반대의 경우도 남아있습니다. 건전한 체계이면서 동시에 건전성의 역도 증명이 가능하다면 그 체계는, 진리와 증명의 관점이 서로 상호교환가능한 매우 완전한 체계일 겁니다. 그래서, 건전성이 성립할때 $\Gamma\models\alpha\Longrightarrow\Gamma\vdash\alpha$가 성립하는 논리학 체계를 완전한 체계라고 합니다. 건전성과 완전성이 성립하면 $\models$와 $\vdash$를 상호교환해서 언제든 쓰고 싶을 때 쓸 수 있습니다. 그래서 논리학에서는 $\models$만 사용하는 분야와 $\vdash$만 사용하는 분야가 나뉘어 있습니다. 전자를 모형론이라고 하고, 후자를 증명론이라고 합니다. 모형이란 개념은 철학에서는 거의 언급되지 않고 수학에서 주로 언급되는데, 우리가 다루었던 해석 $\mathcal{I}$를 수학에서는 구조(Structure) 또는 모형(model)으로 부릅니다. 다른 말로는 의미론과 구문론이라고도 부릅니다. $\models$는 무언가 진리, 참이라는 개념에 의존해있는 것 같고, $\vdash$는 구문론 즉, 어떤 글자들로부터 글자를 추론해내는 구문규칙에 의존해있는 것 같기 때문입니다.

* 건전성과 완전성을 구분해서 쓰기도 하지만, 많은 경우 건전성+완전성 = 완전성으로 표기하는 경우가 많으니 유의하시길 바랍니다.

 술어논리의 건전성, 완전성을 보이는 건 쉽지 않은 일입니다. 엄밀히 개념정의를 하고 증명하려면 수학적으로도 복잡하고 수학과 학부 3-4학년 수준이기 때문에 우리가 이걸 직접 증명할 수는 없습니다. 그러나 위에서 사용되는 건전성, 완전성 형태와 동치인, 좀더 간단한 형태들이 있다는 걸 보일 겁니다. 이를 위해선 아래의 성질들이 필요합니다. 

증명가능성과 관련하여 얻어낼 수 있는 몇 가지 성질들과 필요한 정의들이 있습니다. $\Gamma$는 임의의 문장들의 집합 $\alpha$, $\beta$는 임의의 문장이라고 합시다.

(0) $\alpha\in\Gamma$인 경우 $\Gamma\vdash\alpha$

(0')$\Gamma\vdash\alpha$이고 $\Gamma\subseteq\Gamma'$이면 $\Gamma'\vdash\alpha$ 

(1)$\Gamma\vdash\alpha$이고 $\Gamma\vdash\beta$는 $\Gamma\vdash\alpha\wedge\beta$와 동치

(1')$\Gamma\vdash\alpha\rightarrow (\beta\wedge\neg\beta)$이면 $\Gamma\vdash\neg\alpha$

(2)$\Gamma\cup\{\alpha\}\vdash\beta\Longleftrightarrow\Gamma\vdash\alpha\rightarrow\beta$

(3)$\Gamma$가 비일관적/모순적(inconsistent)라는 말의 정의는 어떤 문장 $\alpha$가 있어서 $\Gamma\vdash\alpha$이고 $\Gamma\vdash\neg\alpha$라는 말입니다.

(4)$\Gamma$가 일관적/무모순적(consistent)라는 말은 그런 문장이 없다는 말입니다.

(5)$\Gamma\vdash\alpha\Longleftrightarrow\Gamma\cup\{\neg\alpha\}\text{는 비일관적}$

(6)$\Gamma\vdash\neg\alpha\Longleftrightarrow\Gamma\cup\{\alpha\}\text{는 비일관적}$

3,4는 정의이고 나머지는 모든 추론체계에서 증명가능한 것들입니다. 증명이란 개념만을 개괄적으로 가지고 증명의 개요를 봅시다.

(0) 문장들의 집합에 속하는 문장은 문장들의 집합으로부터 도출가능하다는 말입니다. 당연한 말이죠. 이미 주어진 것으로부터 주어진 것을 산출해내는 것은 그저 집합에 있는 글자를 써내려가는 것에 불과하기 때문입니다. 우리가 앞에서 내린 증명의 정의를 따라가면, 그냥 $<\alpha>$를 쓰면 끝납니다. $\alpha$가 $\Gamma$의 원소이기 때문에.. 

(0') 작은 집합에서 증명되면 더 큰 집합에서도 증명된다는 말입니다. 당연한 말입니다. 가령, $\{A,B\}$에서 $D$가 증명됐다고 합시다. 그러면 $\{A,B,C\}$에서도 $D$가 증명될 겁니다. $A,B$만 가지고도 증명되던 게 갑자기 $C$를 추가한다고 증명이 안 된다는 건 이상하니까요. 그냥, $A,B$에서 $D$를 증명할 때 썼던 증명식들이 있다면 $A,B,C$에서도 그대로 쓰면 됩니다.

(1) $\alpha$와 $\beta$가 $\Gamma$로부터 증명가능하다고 합시다. 그러면 $\Gamma$에서 $\alpha$와 $\beta$가 증명된 것입니다. 즉, $\alpha$이고 $\beta$이다가 증명된 것이죠. 이 말은, $\alpha\wedge\beta$가 증명되었다는 말입니다. 좀더 앞에서 제시한 증명이란 개념에 맞추어서 보면, $\Gamma$에서 $\alpha$를 증명하는데 쓰인 문장들이 있을 겁니다. $\beta$에 대해서도 동일하겠죠. 가령, $\alpha_1, \alpha_2, ... \alpha_m$을 통해 $\alpha_m= \alpha$임을 추론해냈고, $\beta_1, \beta_2, ..., \beta_n$을 통해 $\beta_n = \beta$임을 추론해냈다고 합시다. 그러면, 그냥 두 문장을 증명하는데 쓰인 문장들의 나열을 그냥 이어주고, 마지막에 $\alpha\wedge\beta$를 쓰면 됩니다. 즉, $\alpha_1, ..., \alpha_m, \beta_1, ..., \beta_n, \alpha_m\wedge\beta_n$를 적으면 증명이 됩니다. 물론 추론체계에서 $\alpha$와 $\beta$가 문장들의 나열 속에 있으면 $\alpha\wedge\beta$를 허용하는 규칙이 있어야 하겠습니다만 이는 어느 체계에서든 직접적으로든, 간접적인 방식으로든 들어가 있습니다. 그러면 $\Gamma\vdash\alpha$와 $\Gamma\vdash\beta$로부터 $\Gamma\vdash\alpha\wedge\beta$를 증명할 수 있습니다. 역도 성립합니다. 어느 추론체계든 $\alpha\wedge\beta$에서 $\alpha$와 $\beta$를 각각 추론하게 허용합니다. 알파이고 베타이다가 증명되는데, 각각이 증명되도록 허락되지 않은 체계는 개념적으로 이상하겠죠.

(1') $\Gamma$에서 $\alpha$를 가정했을 때 모순이 생기면 가정한 $\alpha$가 틀렸다고 볼 수 있으므로 그의 부정인 $\neg\alpha$를 추론한다는 의미입니다. 귀류법의 전형적인 형태입니다.

(2) 이를 연역정리(deduction theorem)이라고 부릅니다. (2) 식의 의미는 간단합니다. $A\rightarrow B$같은 조건문이 의미론에서는 $A$가 참이면 $B$도 참이라는 것으로 이해되지만, 구문론에서는 $A$라는 글자가 주어지면 그에 추론규칙을 사용하여 $B$를 얻어낼 수 있다는 것으로 이해됩니다. 이는 후에 설명할 완전성 정리에 의해 같은 의미를 지님을 좀더 명확히 알 수 있습니다. 어쨌든, 이 개념을 사용해서 연역정리를 풀이해봅시다.

(2)식의 앞부분은 "$\Gamma$와 $\alpha$에 추론규칙을 사용하면 $\beta$를 얻어낼 수 있다"

(2)식의 뒷부분은 "$\Gamma$가 주어졌을 때, $\alpha$가 주어지면 $\beta$를 얻어낼 수 있다"

 가 됩니다. $\alpha$가 앞에 있느냐 뒤에 있느냐의 차이일 뿐이지 의미차이는 없습니다. 가령, 소크라테스에 대한 논증을 빌려옵니다. 사람은 죽는다, 소크라테스는 사람이다, 소크라테스는 죽는다는 문장들이 있습니다. 각각 $A,B,C$로 둡시다. $\Gamma=\{A\}$라고 합시다. 그러면 의미를 쉽게 파악할 수 있습니다. 사람은 죽기 마련이고 소크라테스는 사람이라면, 당연히 소크라테스는 죽을 겁니다. 이 말은 사람은 죽기 마련일 때, 소크라테스는 사람이라면 소크라테스는 죽을 것이다 라는 말과 같은 말입니다. 전제를 조건문을 사용해서 문장에 넣느냐, 아니면 집합 안에 넣어두느냐의 차이일 뿐입니다.

(3), (4)는 정의입니다. 비일관적인 집합은 어떤 문장과 그 문장의 부정을 동시에 증명합니다. 즉, 모순을 증명합니다. 일관적인 집합은 그런 경우가 생기지 않는다는 말입니다.

(5), (6) 예전에 $\models$와 만족가능성에 관해서 비슷한 형태의 증명을 했습니다. 이름이 단지 $\models$가 $\vdash$로 바뀌고 일관성/비일관성이 만족가능성/만족불가능성으로 바뀌었을 뿐입니다.

 증명형식은 같기 때문에 (6)만 봅시다.

$\Gamma\vdash\neg\alpha$라고 합시다. $\Gamma\cup\{\alpha\}$를 살펴봅시다. 우선 $\Gamma\subseteq\Gamma\cup\{\alpha\}$이기 때문에 우리는, $\Gamma\vdash\neg\alpha$와 (0')으로부터 $\Gamma\cup\{\alpha\}\vdash\neg\alpha$임을 알 수 있습니다. 그런데 이 집합에는 $\Gamma\cup\{\alpha\}$에는 $\alpha$가 있기 때문에, (0)으로부터 $\Gamma\cup\{\alpha\}\vdash\alpha$임을 알 수 있습니다. 즉, 우리는 $\Gamma\cup\{\alpha\}$가 비일관적인 집합이라는 것을 알 수 있습니다.

 반대를 가정합시다. 즉, $\Gamma\cup\{\alpha\}$가 비일관적이라고 합시다. 그렇다면, 어떤 문장 $\beta$가 있어서 우리는 해당 문장들의 집합에서 $\beta\wedge\neg\beta$를 증명할 수 있습니다. 이는 비일관성의 정의와 (1)을 사용한 것입니다. 즉, $\Gamma\cup\{\alpha\}\vdash\beta\wedge\neg\beta$를 얻어낼 수 있고, 여기에 연역정리(2)를 사용하면 $\Gamma\vdash\alpha\rightarrow (\beta\wedge\neg\beta)$를 얻을 수 있습니다. 귀류법(1')을 사용하면 $\Gamma\vdash\neg\alpha$를 얻을 수 있습니다.

 따라서 원하는 것이 모두 증명되었습니다.

(5),(6)을 사용하면 예전에 논리적 함축과 만족가능성의 개념이 상호교환하다는 것을 증명할 수 있었듯이, 도출가능성/증명가능성이 일관성과 개념적으로 상호교환가능하다는 걸 알 수 있습니다. 굳이 여기서 쓰진 않겠습니다만 증명의 형태는 논리적함축과 만족가능성에서 했던 양식을 따라간다는 것만 적어두겠습니다.

 이제, 건전성과 완전성을 다른 형태로 나타낼 수 있습니다. 논리적 함축은 만족가능성의 문제로, 도출가능성은 일관성의 문제로 환원시키는 겁니다. 건전성부터 봅시다.

건전성 정리1 : 임의의 문장들의 집합과 임의의 문장에 대해, 그 문장이 문장들의 집합으로부터 증명되면 둘 사이에는 논리적 함축관계가 성립한다.

건전성 정리2: $\Gamma$는 임의의 문장들의 집합, $\alpha$는 임의의 문장이라고 할 때, $\Gamma\vdash\alpha\Longrightarrow\Gamma\models\alpha$

건전성 정리3 : $\Gamma$는 임의의 문장들의 집합, $\alpha$는 임의의 문장이라고 할 때, $\Gamma\cup\{\neg\alpha\}$가 비일관적이면, $\Gamma\cup\{\neg\alpha\}$는 만족불가능하다

건전성 정리4 : $\Gamma$는 임의의 문장들의 집합, $\alpha$는 임의의 문장이라고 할 때, $\Gamma\cup\{\neg\alpha\}$가 만족가능하면, $\Gamma\cup\{\neg\alpha\}$는 일관적이다

건전성 정리5 : $\Gamma$가 임의의 문장들의 집합일 때, $\Gamma$가 만족가능하면, $\Gamma$는 일관적이다 

 2는 1을 기호로 나타낸 것이고, 3는 2에 나타난 $\models$와 $\vdash$를 동치인 조건으로 바꾼 것입니다. 4는 3에 대우를 취한 것입니다(즉 $\neg B\rightarrow\neg A$이면 $A\rightarrow B$). 4의 형태를 더 단순히 바꿀 수 있느냐가 문제가 됩니다. 즉, 5로 바꾸는 게 문제가 됩니다. 4와 5가 동치임을 봅시다.

 가장 중요한 건 모든 $\Gamma$와 $\alpha$에 대해 4가 성립한다는 것이고, 5는 모든 $\Gamma$에 대해 성립한다는 것입니다.

 우선 4를 가정합시다. 우리는 1-4가 모두 동치임을 알기 때문에 사실 아무거나 사용하면 됩니다. 5의 대우를 대신 증명합시다. 즉, $\Gamma$가 비일관적이면, $\Gamma$가 만족가능하다는 걸 보입시다. $\Gamma$가 비일관적이면, 어떤 $\alpha$가 있어 $\Gamma\vdash\alpha$이고 $\Gamma\vdash\neg\alpha$입니다. 4은 2와 동치이므로 2를 사용하면, 우리는 $\Gamma\models\alpha$와 $\Gamma\models\neg\alpha$를 얻습니다. 이때 $\Gamma$를 만족가능하게 하는 해석이 존재한다고 합시다. 이를 $\mathcal{I}$라고 합시다. 그런데 $\Gamma\models\alpha$, $\Gamma\models\neg\alpha$와 $\mathcal{I}\models\Gamma$에 의해서 $\mathcal{I}$는 $\alpha$와 $\neg\alpha$를 모두 참으로 만들어야 하고 이는 모순입니다. 우리는 $\Gamma$가 만족가능하다는 가정에서 출발하여 모순을 낳았으므로 귀류법에 의해 $\Gamma$는 만족불가능합니다. 따라서 4로부터 5를 얻어냈습니다.

 마지막으로, 5에서 4를 증명하면 됩니다. 그런데 5에서 4는 자동적으로 증명됩니다. 5는 임의의 문장들의 집합에 대해 성립하기 때문에, 4를 증명하기 위해 임의의 어떤 $\Gamma\cup\{\alpha\}$를 택하더라도 여전히 이 집합은 문장들의 집합이기 때문에 5를 적용할 수 있습니다.

 따라서 모든 증명이 끝났습니다. 그런데 보통 2와 5만 직접 증명하기 때문에 추가적으로 증명을 쓰도록 하겠습니다. 2에서 5는 위에서 4에서 5로 쓴 것과 같습니다. 4를 가정해서 동치인 2를 이용해서 5를 이끌어냈기 때문입니다. 5에서 2만 보면 됩니다. 이도 간단합니다. 임의의 $\Gamma$와 $\alpha$에 대해 $\Gamma\vdash\alpha$라고 합시다. 도출가능성과 일관성의 관계에 의해서 $\Gamma\cup\{\neg\alpha\}$는 비일관적입니다. 이 집합은 문장들의 집합이므로 5를 사용할 수 있습니다. 5에 의해서ㅡ5의 대우를 사용하든, 혹은 MT rule($A\rightarrow B$와 $\neg B$로부터 $A$를 도출)을 사용하든ㅡ $\Gamma\cup\{\neg\alpha\}$는 만족불가능합니다. 다시 만족가능성과 논리적 함축의 관계에 의해서 $\Gamma\models\alpha$가 됩니다. 따라서 증명이 끝났습니다.

완전성 정리 : 어떤 문장들의 집합 $\Gamma$를 가져다 놓아도, $\Gamma$가 일관적이면 $\Gamma$는 만족가능하다

 건전성 정리를 했던 것처럼 바꾸고 바꾸고 바꾸어서 하면 이런 결론이 도출됩니다. 증명방식도 위와 크게 다르지 않습니다. 사실 건전성 정리는 위와 같이 바꾸어서 증명하는 건 어렵고, 실제로는 $\vdash\Longrightarrow\models$의 방식으로 증명합니다. 그런데 완전성 정리는 그런 방식으로 괴델이 증명하긴 했지만 매우 복잡하고 별로 중요한 증명방식이 아닙니다. 후에 헨킨은 특히 Henkin Construction이라는 방법을 만들어서 일관성으로부터 만족가능성을 이끌어내는 매우 중요한 해석/모형을 만들어냈고 이것이 모형론의 기반이 되었습니다.

 어쨌든, 건전성+완전성 혹은 완전성 정리(앞으론 건전성+완전성을 완전성으로 쓰겠습니다)로부터 우리가 알 수 있는 건 ㅑ와 ㅏ라는 개념이 일치한다는 것입니다. 또한 만족가능성과 일관성이라는 개념이 일치한다는 것입니다. 또한 $\alpha\models\beta$는 "$\alpha$가 참이면 $\beta$도 언제나 참이다"이고 $\alpha\vdash\beta$는 "$\alpha$에 추론규칙을 사용하여 $\beta$를 얻는다"가 되고, 서로 일치하기 때문에 조건문은 참이라는 개념을 사용해서 생각될수도, 추론규칙의 방식으로도 이해될 수 있습니다. 연역정리로 생각한다면, $\models\alpha\rightarrow\beta$ 그리고 $\vdash\alpha\rightarrow\beta$와 일치하기 때문에 "$\alpha\rightarrow\beta$"의 위와 같이 의미를 정할 수 있습니다.