술어논리(11) ㅡ 불완전성 정리란?

불완전성 정리에 대해 사람들이 너무 부적절하게 생각하는 경향이 있는데 정확히 어떤 의미인지에 대해서 살펴보도록 합시다.

1. 문장들의 집합을 이론(Theory)라고 부르고 $T$로 표기한다

2. 이론 $T$가 완전하다는 것은, $T$가 일관적이고, 임의의 문장 $\alpha$에 대해 $T\vdash\alpha$이거나 $T\vdash\neg\alpha$가 반드시 성립함

 이 부분은 사람마다 초점이 달라서 정의가 조금씩 다릅니다.

 철학 분과에서는 주로 어떤 문장들의 집합 $T$가 이론이라는 말을 $T=Cn(T)$일 때로 주로 정의합니다. $Cn(T)=\{\alpha | T\vdash\alpha\}$이고 $Cn(T)$는 $T$에서 증명가능한 것들, 혹은 완전성 정리에 의해 $T$에서 참인 것들의 집합입니다(Consequence of $T$). 아래에선 $\models$와 $\vdash$를 구분하지 않습니다.

 이 관점에서 이론 $T$는 논리적 함축관계 혹은 증명가능성관계에 있어서 닫혀있다는 말입니다. 이 사람들이 이렇게 정의할 때는, (특정) 수학이론이란 진리관계에 대해서 닫혀있는 것이라고 생각하는 것입니다. 가령 정수론(자연수 관한 수학이론)에서 무언가 결과를 얻어내면 그 결과는 정수론에 그대로 귀속된다는 것입니다. 그래서 정수론은 정수론에서 참인 문장(=증명가능한 문장)들을 포함해야 한다는 것이죠. 이 조건이 $Cn(T)\subseteq T$입니다. 그런데 $T\subseteq Cn(T)$는 너무나 당연한 것이기 때문에 그냥 퉁쳐서 $T=Cn(T)$로 정의하는 겁니다. 증명은 나중에 하도록 하겠습니다.

 제가 여기서 이론을 단순히 문장들의 집합으로 둔 것은 다른 이유가 있습니다. 많은 경우 모형론을 전개하다보면 어떤 이론의 근간이 되는 공리들을 중심으로 하여 이론을 파악하기 때문에, 함축관계에 대해서 닫혀있는지 여부가 아니라 결국 특정한 공리들 자체를 유심히 보는 경우가 많기 때문입니다. 예전에 본 $PA$ 공리체계도 그렇고, 다양한 체계들에 대해서 각 공리들 자체가 중요할 때가 많습니다. 그래서 저는 이론을 그냥 문장들의 집합으로 봅니다. 또한 적지 않은 모형론 책들이 그렇게 합니다.

 이론 $T$가 완전하다는 것에 대해 저는 일관성을 유지하면서, 임의의 문장을 주면 그 문장이 증명되거나 반드시 반증되는 것으로 정의했습니다. 사람에 따라 일관성을 완전성에 포함시키지 않는 경우도 심심치 않게 발견됩니다. 그런 경우는 제가 정의한 방식을 말하려면 '일관적이고 완전한 이론'이라고 말해야 합니다. 이론의 완전함이라는 걸 어떻게 이해하느냐의 차이일 뿐입니다. 참고로 이는 논리학의 완전성 정리와는 아무 관련이 없습니다. 완전성 정리의 완전성은 주어진 논리체계의 만족가능성과 일관성 개념이 일치하는지를 묻는 개념이고, 지금 우리가 다루는 완전성은 이미 주어진 논리체계 안에서 특정 이론이 임의의 문장을 주었을 때 증명이나 반증을 항상 할 수 있느냐를 묻는 것이기 때문에 완전 다른 개념입니다. 헷갈리지 않도록 유의하시길 바랍니다. 어쨌든, 완전성이란 개념에 대해 좀 이해하기 위해서 몇 가지 정리와 예시들을 봅시다.

다루고자 하는 언어 $\mathcal{L}$과 모형 $\mathcal{M}, \mathcal{N}$(=해석), 이론 $T$가 주어져 있을 때,

0. $T\subseteq Cn(T)$

1. $Th(\mathcal{M})=\{\alpha | \mathcal{M}\models\alpha\}$은 완전하다

2. $Cn(T)=Cn(Cn(T))$

3. $Th(\mathcal{M})\subseteq Th(\mathcal{N})$이면 $Th(\mathcal{M}) = Th(\mathcal{N})$

4. $T$가 완전하고 $\mathcal{M}, \mathcal{N}\models T$라면 $Cn(T)=Th(\mathcal{M}) = Th(\mathcal{N})$

($Th(\mathcal{M}) = Th(\mathcal{N})$를 줄여서 $\mathcal{M}\equiv\mathcal{N}$(M is equivalent to N)

0. 당연한 말입니다. $\alpha$가 $T$의 원소면, $Cn(T)$는 $T$의 논리적 귀결(논리적 함축)의 집합이기 때문에, 당연히 참으로 만들어야겠죠. 엄밀히는, 임의의 $\mathcal{M}\models T$인 $\mathcal{M}$은 $T$의 원소인 $\alpha$를 참으로 만들고 $T\models\alpha$가 성립합니다.

1. $Th(\mathcal{M})$은 모형의 이론(Theory of model)이라는 말로 주어진 모형에서 참인 문장들의 집합입니다. $\mathcal{M}$에서 참인 문장들의 집합이기 때문에, $\mathcal{M}$이 당연히 그 모형이 될 것이므로, 완전성 정리에 의해 $Th(\mathcal{M})$는 일관적입니다. 또한 모형에서 어떤 문장이 주어지든, 그 문장은 모형 안에서 참이거나 참이 아닙니다. 모형에서 참이 아닌 것은 거짓으로 개념적으로 정의되기 때문에, 모형은 모든 문장을 참 혹은 거짓으로 만듭니다. 따라서 임의의 문장 $\alpha$가 주어졌을 때, $\alpha$가 $\mathcal{M}$에서 참이면 $\alpha$가 $Th(\mathcal{M})$원소가 되고, $\neg\alpha$가 $\mathcal{M}$에서 참이면 $\neg\alpha$가 $Th(\mathcal{M})$의 원소가 됩니다. 원소가 되면 당연히 증명가능하기 때문에 $Th(\mathcal{M})$는 완전한 이론입니다.

2. 이것도 당연한 말입니다. T에서 증명가능한 것들을 모두 모은 집합은, 당연히 T에서 증명가능한 것들을 모두 모은 집합에서 증명가능한 것들이 집합과 일치하겠죠. 굳이 증명을 한다면, 우선 0에 의해서 한쪽 방향은 증명이 됩니다. $Cn(T)$도 문장들의 집합인 이론이기 때문입니다. 반대로, $Cn(Cn(T))\subseteq Cn(T)$를 보이면 됩니다. $\alpha$가 앞의 것의 원소라고 합시다. 그러면 $Cn(T)\models\alpha$입니다. 이제 $T\models\alpha$를 보이면 됩니다. $\mathcal{M}\models T$인 임의의 모형을 가져옵시다. 그러면 $\mathcal{M}\models Cn(T)$입니다. $Cn(T)$의 원소는 $T$와 논리적 함축관계인 것들인데, $\mathcal{M}$은 $T$를 만족하기 때문에 그 함축관계에 있는 원소들도 당연히 참으로 만듭니다. 따라서 $\alpha$도 참으로 만들고. 우리는 조건을 만족하는 $\mathcal{M}$이 $\alpha$를 만족하는 걸 보였기 때문에 증명이 완료됩니다.

3. 당연한 말입니다. 둘다 완전한 이론인데, 완전하다는 건 어떤 문장을 놓아도 참이거나 거짓으로 만든다는 것이고, 한쪽이 다른 한쪽의 부분집합이면 임의의 문장에 대해 그런 성질이 성립하는 것이 그대로 들어가기 때문에 어떤 문장에 대해 서로 불일치가 일어날 수 없습니다.

 증명으로 봅시다. $\mathcal{N}$의 원소인 $\alpha$가 있다고 합시다. 즉, $\mathcal{N}\models\alpha$입니다.

$\alpha$가 $\mathcal{M}$에서 참이면, $\alpha\in Th(\mathcal{M})$이므로 문제가 없습니다. 또한, $\alpha$가 $\mathcal{M}$에서 거짓이면 $\mathcal{M}\models\neg\alpha$이고 따라서 $\neg\alpha\in Th(\mathcal{M})$의 원소입니다. 전제에 의해서 다시 $\neg\alpha\in Th(\mathcal{N})$이고 이는 정의에 의해 $\mathcal(N)\models\neg\alpha$인데, 한 모형은 어떤 문장과 그 문장의 부정을 동시에 참으로 만들 수 없습니다. 따라서 모순입니다. 따라서 이런 경우는 발생하지 않기 때문에 앞의 경우만 가능하게 되고 증명이 완료됩니다.

4. 이 부분이 중요합니다. 모형론에서는 중요하게 어떤 이론이 완전한지 아닌지를 따집니다. 완전한 이론이라면 한 모형만을 가지고 그 이론에서 참인 문장과 거짓인 문장을 모두 가려낼 수 있기 때문입니다. 물론 어떤 문장에 이론 안에서 참인지, 혹은 거짓인지를 모두 가려낼 수 있다고 해서 그것이 최상인 건 아닙니다. 완전한 이론을 참으로 만드는 모형들의 구조가 서로 다를 수 있습니다. 그런 문제는 너무 복잡하기 때문에 여기서 다룰 수 없습니다..

 $Cn(T)= Th(\mathcal{M})$인 경우만 다루면 됩니다. 어차피 $\mathcal{M}$은 조건을 만족하는 임의의 모형이기 때문에, 나중에 조건을 만족하는 아무 $\mathcal{N}$을 추가하면 어차피 $Cn(T) = Th(\mathcal{N})$이 될 것이므로 결국 다 같게 됩니다.

 $Cn(T)\subseteq Th(\mathcal{M})$을 봅시다. $T\models\alpha$라고 합시다. 그런데, $\mathcal{M}\models T$이기 때문에, 논리적 함축관계에 의해 $\mathcal{M}\models\alpha$가 되고, 정의에 의해 $\alpha\in Th(\mathcal{N})$이 됩니다. 따라서 부분집합관계가 성립합니다.

 역인 $Th(\mathcal{M})\subseteq Cn(T)$를 봅시다. $\mathcal{M}\models\alpha$라고 합시다. $T$는 완전하기 때문에 $T\models\alpha$ 혹은 $T\models\neg\alpha$가 성립합니다. 후자인 경우 $\mathcal{M}\models T$이기 때문에 논리적 함축관계에 의해서 $\mathcal{M}\models\neg\alpha$가 되고 한 모형이 어떤 문장과 그 문장의 부정을 참으로 만들어야하는 모순이 생깁니다. 따라서 이 경우는 발생할 수 없고, $T\models\alpha$만이 남습니다. 이는 정의에 의해 $\alpha\in Cn(T)$를 의미합니다. 따라서 증명이 끝났습니다.

 모형의 이론은 언제나 완전하지만, 모형의 이론이 아닌 아무 문장들이나 모아둔 이론은 수학적으로 불안전한 이론들일 확률이 정말 높겠죠. 따라서 불안전한 이론의 존재가 이상할 게 하나도 없습니다. 오히려 완전한 이론이 특수한 경우에 속하고 이걸 발견하는 게 중요한 겁니다. 가령 완전한 이론들의 예시는 다음과 같습니다.

1. 유클리드 기하학 : 여기서 논리기호를 사용한 공리체계를 제시하지는 않겠습니다만 완전한 이론으로 증명되었습니다

2. 프레스버거 공리계 : PA에서 곱셈과 크기관계 기호를 제거하고 그에 관련한 공리들을 제거한 이론. 즉, 비논리상항이 0, 1, +로만 이루어진 자연수이론.

3. DLO/ep : Dense Linear Order without endpoints.. 비논리상항이 <만 있고, x축만 있을 때 실수가 있을 때 -와 +로 끝없이 퍼져나가는 성질을 나타낸 이론입니다. 굳이 알 필요는 없으나 공리는 아래와 같습니다.

Axiom 1 (Linear order). ∀x∀y(x < y ∨ y < x ∨ y = x)

Axiom 2 (Linear order) ∀x(¬x < x)

Axiom 3 (Transitivity) ∀x∀y∀z(x < y ∧ y < z→x < z)

Axiom 4 (Without endpoints). ∀x(∃y)(y < x)

Axiom 5 (Without endpoints). ∀x(∃y)(x < y)

Axiom 6 (Dense) ∀x∀y(x < y→(∃z)(x < z ∧ z < y))

 안타깝게도, DLO 즉 공리4,5를 뺀 단순한 Dense Linear Order는 불완전한 이론입니다. 왜냐면 DLO에서도 [0,1)처럼 한쪽은 끝점이 없는 경우와 (0,1)처럼 둘다 끝점이 없는 경우가 문장으로 표현될 수 있고 하나가 참이면 다른 하나는 거짓이기 때문에 DLO를 만족하는 모형들 사이에 서로 다른 문장이 참이 되는 경우가 생기고 따라서 위의 4번에 의해서(MT rule을 쓰든 대우를 취하든) 완전하지 않은 이론이 됩니다.

 사실 이 외에도 수많은 좋은 불완전한 이론과 완전한 이론들의 예시가 있으나 대수학 등을 공부하지 않는 이상 쉬운 것들이 없어서 쉬운 예시는 여기까지 합시다. 이제 불완전성 정리에 대해서 볼 겁니다. 불완전성 정리는 20세기 초반에 완전할 것이라 믿어지던 몇 가지 이론들이 그렇지 않다는 것이 밝혀짐으로서 스포트라이트를 받은 결과입니다. 가장 단순한 형태로는 우리가 예전에 공리계로 써놓았던 $PA$가 불완전하다는 것입니다. 수학의 전형적인 이론 중에 하나가 정수론이었고 예전에는 중요한 수학이론들에 대한 기대치가 높았기 때문에, 어떤 정수론적인 문장이 주어지더라도 공리에 의해서 그것을 증명하거나, 언젠가는 그것의 부정을 증명(반증)할 수 있다고 믿었습니다. 그러나 괴델에 의해서 거짓으로 밝혀졌습니다. 우리가 앞에서 볼 수 있듯이, 완전한 이론이란 어떤 문장을 내놓아도, 그것이나 그것의 부정을 증명할 수 있습니다. 불완전한 이론은 그렇지 않은 이론입니다. 즉, 어떤 문장이 있어서 그 문장과 그 문장의 부정을 이론이 모두 증명하지 못합니다. 기호로 쓰면 $T\not\vdash\alpha$이면서 $T\not\vdash\neg\alpha$인 $\alpha$가 존재한다는 것입니다. 그렇다면, 공리를 사용해서 정수론을 전개하는 사람들은 자신이 증명이나 반증하고 싶어하는 어려운 문장이 나왔을 때 둘다 되지 않음에도 영원히 삽질하는 일이 생길수도 있게 됩니다. 실제로 요즘 수학에서는 좀 많이 안풀린다 싶으면 이거 증명도 반증도 안 되는 문장아니야?를 많이 의심합니다. 그렇게 해서 밝혀진 문장도 확실히 존재합니다. 가령 정수론에서는 굿스타인 정리 같이 PA에서는 증명이 안되는 문장들이 있음이 밝혀졌습니다. 굳이 굿스타인 정리를 검색하시지는 마세요.. 꽤 간단한 편이지만 그래도 복잡합니다..

 불완전한 이론이 의미하는 바는 완전성 정리에 의해서 드러납니다. ㅏ를 ㅑ로 바꾸면, $T\not\models\alpha$와 $T\not\models\neg\alpha$가 되고, 이 말은 $T$를 참으로 만들지만 $\alpha$를 거짓으로 만드는 모형이 하나 존재하고, 또 $T$를 참으로 만들지만 $\neg\alpha$를 거짓으로 만드는 다른 모형이 존재한다는 말입니다. 즉 특정 이론에 대해 추론체계를 사용해서는 증명도 반증(주어진 문장의 부정의 증명)도 안 되지만, 특정한 모형 하에서는 참이고, 또한 특정한 모형에서는 거짓인 문장이 존재한다는 말이죠. 세간에 많이 회자되는, 참이지만 증명도 반증도 불가능한 문장이라는 게 이런 말입니다. 정확히는 '특정한 모형 하에서는 참이지만, 추론체계에서 증명도 반증도 안 되는 문장'이라는 거죠.

 괴델이 증명한 건 $PA$에서 그런 문장이 존재한다는 것이었습니다. 정확히 말하면, 표준적인 자연수 모형$\mathbb{N}$에서는 만족가능/참이지만, $PA$에선 증명이나 반증이 안되는 문장이 존재한다는 것이었죠. 그게 제1불완전성 정리이고, 제2불완전성 정리는 $PA$의 일관성을 $PA$의 언어와 $PA$ 공리 안에서 증명할 수 없다는 것이었습니다. 지금 수학하는 사람들의 입장에서야 뭐 스스로의 일관성/무모순성을 자신이 증명한다는 게 뭔가 이상해보이지만, 20세기 초에는 그게 수학이 흠결없는 세계라고 수학자들이 믿던 때였기 때문에 더욱 이 정리가 쇼크였습니다.

 그리고 $PA$보다도 더 중요한 건 수학 자체의 일관성의 문제입니다. 괴델의 정리에서 쓰인 증명을 적당히 잘 조작하면, 현대 수학의 근간이 되는 집합론의 공리체계(ZF 집합론이라고 부릅니다)에다가 비슷한 논리를 적용해서 ZF가 불완전한 체계이며, 또한 ZF에서 ZF의 일관성을 증명할 수 없다는 걸 보일 수 있습니다. 이게 불완전성 정리에서 가장 중요한 결론이었죠. 그래서 수학은 완전하지 않습니다. 정확히 말하면 특정 집합론 공리계를 가지고 수학을 하다보면 원론적으로 막히는 부분이 생길 수밖에 없습니다. 그러면 어떻게 해야 할까요? 첫째로 그 막힌 부분이 다른 공리들을 추가하거나 다른 여러 가지 방법을 써서 기존 수학공리체계에서 증명도 반증도 안 됨(독립적)을 보입니다. 그리고 편의에 따라 그 문장을 배제하고 쓰던지, 아니면 그 문장이나 그 문장의 부정을 기존의 체계에 더해서 좀더 확장된 방식의 수학을 하든지 하면 됩니다.

 가령 ZF에서는 선택공리(AC, Axiom of Choice)라는 게 있습니다. 공집합이 아닌 집합들을 나열했을 때, 그 집합들에서 원소를 하나씩 뽑아서 새로운 집합을 만들 수 있다는 공리입니다. 직관적으로 참인 것처럼 보이지만 실상은 이 공리는 기존의 다른 집합공리들로부터 증명도 반증도 되지 않습니다. 좀더 쉽게 말하면, 선택공리가 거짓이 되는 집합론의 모형을 찾을 수 있고, 선택공리가 참이 되지 않는 집합론의 모형도 찾을 수 있다는 말입니다.

 마지막으로 이런 질문을 던져볼 수 있습니다. $PA$에서 비표준적인 모형들이 존재한다면, $PA$에서 공리를 늘리다보면 표준적인 자연수모형을 포착할 수 있는 공리체계를 만들 수 있지 않을까? 현대적인 괴델의 불완전성 정리 풀이를 하는 와중에 이것은 불가하다는 걸 증명하게 됩니다. 여기서 적을 순 없지만 표준적 자연수모형에서 참인 문장들의 집합인 $Th(\mathbb{N})$는 공리화가 불가능합니다. 어떤 이론 $T$가 공리화가능하다는 말은, $S$라는 이론이 있어서 $Cn(S)=Cn(T)$이고 또한 $S$의 모든 원소를 컴퓨터를 통해 명확히 제시할 수 있다는 말입니다. 물론 여기서 $S$(공리들의 집합, 공리체계)는 사실상 $T$보다 작은 집합일 것입니다. 실질적인 의미는 $T$에서 증명가능한 모든 문장을 포착할 수 있는 어떤 작은 이론이 있고 그 이론이 무엇인지 실제적으로 파악할 수 있다는 말입니다.

 여러 결과에 따르면 표준적인 자연수 모형 $\mathbb{N}$은 공리화가 불가능합니다. 즉, $PA$에 셀 수 없이 많은 문장들을 새로 추가하더라도ㅡ그것이 일관적인 한ㅡ 표준적인 자연수 모형에 대한 공리체계가 될 수 없습니다. 신기하죠?