술어논리(10) ㅡ 조밀성 정리

조밀성 정리 : $\Gamma$가 임의의 문장들의 집합일 때, $\Gamma_0\subseteq\Gamma$인 임의의 유한집합이 만족가능하다는 것은 $\Gamma$가 만족가능하다는 것과 동치이다

 Compactness Theorem이라고 부르는 이 정리는 모형론의 근본적인 정리 중에 하나입니다. 어떤 집합의 만족가능성을 따지기 위해서 집합 전체를 따질 필요가 없이 유한한 부분집합들이 모두 만족가능한지만 확인하면 되기 때문입니다. 이에 대한 증명을 봅시다.

 우선, $\Gamma$가 만족가능하면 그에 대한 모형(=해석)이 존재할 것이고 그 모형이 $\Gamma$의 부분집합들을 참으로 만들 겁니다. $\Gamma$가 모형 하에서 참이기 때문에 그 임의의 부분집합도 당연히 참이 되겠죠.

 역으로, $\Gamma$의 임의의 유한한 부분집합들이 모두 만족가능하다고 합시다. 그런데 $\Gamma$가 만족가능하지 않다고 합시다. 그러면 완전성 정리에 의해 $\Gamma$는 비일관적이고, 따라서 어떤 $\alpha$가 있어서 $\Gamma\vdash\alpha\wedge\neg\alpha$입니다. $\beta = \alpha\wedge\neg\alpha$라고 합시다. 그러면 도출가능성의 정의에 의해서 어떤 문장들의 나열 $<\beta_1, ..., =\beta_n>$이 있어서 정의를 만족하고 $\beta_n = \beta$가 됩니다. 증명이란 건 근본적으로 유한한 문장들에 추론규칙을 유한번 적용하여 얻어지는 유한한 절차입니다. 즉, $\Gamma$가 아무리 큰 무한집합이라고 할지라도 $\beta$를 이끌어내는데는 위와 같이 유한한 문장들만 사용합니다. 우리는 $\Gamma$에서 $\beta$를 증명하는데 사용된  $\beta_1, ..., \beta_n$ 중에서 $\Gamma$의 원소들을 뽑아서 $\Gamma_0$라고 합시다. 이는 당연히 유한집합입니다. $\Gamma$에서 실질적으로 $\beta$를 이끌어내는데 사용된 원소들을 뽑아내겠다는 거죠. 즉, 불필요한 원소들을 제외하는 건데, 증명에 쓰였던 원소들만 뽑아냈기 때문에 $\Gamma_0$만으로도 $\beta$가 증명이 되는 건 당연한 일입니다. 즉, $\Gamma_0\vdash\beta$입니다. 이에 완전성 정리를 사용하면 $\Gamma_0\models\beta$가 됩니다. 가정에 의해서 $\Gamma_0$가 유한하기 때문에 만족가능합니다. 이에 대한 해석을 $\mathcal{I}$라고 합시다. $\Gamma_0\models\beta$에 의해 $\mathcal{I}\models\beta$가 될 것인데, $\beta$는 $\alpha\wedge\neg\alpha$입니다. 해석은 어떤 문장과 그 문장의 부정을 동시에 만족시킬 수 없기 때문에 모순이 생깁니다. 따라서 처음에 가정한 $\Gamma$가 만족가능하지 않다는 것이 틀렸습니다. 귀류법에 의해 원하는 것을 우리가 원하는 것을 얻게 됩니다.

 조밀성 정리는 자연수체계에 대한 비표준적인 모형/해석을 제공하는데 쓰일 수 있습니다. 가령 어떤 자연수보다 더 큰 자연수라는 개념을 정의할 수 있게 만듭니다. 아래는 자연수공리계인 페아노 공리계(Peano axioms)입니다. 모형론이 발달하기 전까지는 아래의 공리들을 만족하는 집합은 우리가 아는 $\mathbb{N}=\{0,1,2,3,...\}$밖에 없다고 생각했습니다. 제가 지금까지 0을 자연수에 포함시키지 않아왔는데, 교양~전공입문 수준의 논리학을 배우시는 분들은 0을 자연수에 넣는 것에 익숙하지 않기 때문이었습니다. 수학분과마다 정의가 다르긴 하지만, 공리계적인 접근에서는 0을 자연수로 넣는 게 관례입니다. 이에 대한 이유를 설명하는 건 복잡하기 때문에 건너 뜁시다.. 여튼, 아래를 만족하는 모형은 우리가 아는 표준적인 자연수집합에 대한 모형밖에 없다고 생각했었습니다. 그런데 조밀성 정리를 사용하면 재밌는 발견을 할 수 있습니다.

$1. {\displaystyle \forall x,y,z\ ((x+y)+z=x+(y+z))}$

$2.{\displaystyle \forall x,y\ (x+y=y+x)}$

$3.{\displaystyle \forall x,y,z\ ((x\cdot y)\cdot z=x\cdot (y\cdot z))}$

$4.{\displaystyle \forall x,y\ (x\cdot y=y\cdot x)}$

$5.{\displaystyle \forall x,y,z\ (x\cdot (y+z)=(x\cdot y)+(x\cdot z))}$

$6.{\displaystyle \forall x\ (x+0=x\land x\cdot 0=0)}$

$7.{\displaystyle \forall x\ (x\cdot 1=x)}$

$8.{\displaystyle \forall x,y,z\ (x<y\land y<z\Rightarrow x<z)}$

$9.{\displaystyle \forall x\ (\neg (x<x))}$

$10.{\displaystyle \forall x,y\ (x<y\lor x=y\lor y<x)}$

$11.{\displaystyle \forall x,y,z\ (x<y\Rightarrow x+z<y+z)}$

$12.{\displaystyle \forall x,y,z\ (0<z\land x<y\Rightarrow x\cdot z<y\cdot z)}$

$13.{\displaystyle \forall x,y\ (x<y\Rightarrow \exists z\ (x+z=y))}$

$14.{\displaystyle 0<1\land \forall x\ (x>0\Rightarrow x\geq 1)}$

$15.{\displaystyle \forall x\ (x\geq 0)}$

위의 문장들의 집합을 PA라고 합시다. 페아노 공리계의 언어 $\mathcal{L_{PA}}$의 비논리상항에는 $0, 1, +, \cdot, <$가 있습니다. $x\leq y$는 $x<y \vee x=y$의 줄임말입니다.

그리고 언어에 개체상항 $c$를 추가해서 $\{c>1+1+...+1 \text{(1이 n개)} | n\in\mathbb{N}\}$라는 집합을 $\Gamma$로 둡시다. $1+1+...+1$이 n개의 1로 구성되어있을 때 n이라고 구분하지 않고 씁시다. $PA$의 언어에는 각각의 자연수에 대한 개체상항은 없기 때문에 자연수를 나타내려면 1과 덧셈을 사용해야 합니다. 그래서 실제 자연수 n과 이를 논리기호로 표현하는 1+1+...+1는 다르기 때문에 n' 등으로 다르게 써야하지만 굳이 그럴 필요는 없어 보이기에 구분하지 않고 쓰겠습니다.

즉, $c$는 어떤 1+1+1+...+1로도 표현될 수 없는 매우 큰 수(무한히 큰 수)이기를 바라는 것입니다. 조밀성 정리에 의해서 $\Gamma$의 임의의 유한한 부분집합이 만족가능하다는 걸 보이면 $PA$를 만족하면서 어떤 유한한 자연수보다도 더 큰 '비표준적인 자연수'가 있는 모형이 존재한다는 걸 증명하게 됩니다.

 이는 간단합니다. $\mathbb{N}$이 유한한 부분집합들의 모형이 되기 때문입니다. $\Gamma_0$를 $PA\cup\Gamma$의 임의의 유한한 부분집합이라고 합시다. 그러면 $\Gamma$의 원소 중에 택해진 유한한 원소들, 가령 $c>n_1, c>n_2, ..., c>n_i$가 있다고 합시다. $n$을 $n_1, ..., n_i$ 중에서 가장 큰 것에 1을 더한 수라고 합시다. 우리는 지금 표준적 자연수모형 $\mathbb{N}$을 사용하고 있습니다. 그러면, $c$의 해석에 $n$을 부여하면 택해진 유한한 문장들은 참이 됩니다. $\mathbb{N}$는 당연히 PA를 참으로 만들기 때문에 $\Gamma_0$는 $\mathbb{N}$에 의해 만족됩니다. 또한 $\Gamma_0$는 임의였기 때문에 조밀성 정리에 의해서 $PA\cup\Gamma$는 만족가능합니다. 즉, 자연수공리계를 참으로 만들면서 무한한 크기를 가지는 원소를 지닌 '비표준적 자연수 모형'이 존재합니다. 이제 추가된 개체상항 $c$을 언어에서 제외하고 다시 $PA$의 언어로 돌아가더라도, 무한히 큰 원소에 대한 개체상항을 표현하는 언어가 빠지느냐 아니냐의 문제일 뿐 모형의 원소와 구조 자체는 변하지 않기 때문에 아무 문제 없습니다. 따라서 $PA$의 언어에서 비표준적인 자연수모형이 존재합니다.

 모형론에서 흥미로운 것은 표준적 모형과 구조가 다른, 서로 다른 구조의 비표준적 모형들이 얼마나 많이 있는가를 밝힐 수 있다는 점입니다. 집합론을 배우신 분은 실수집합의 크기에 대해 아실 것입니다. 비표준적 모형들의 서로 다른 구조들의 개수는 실수크기만큼 있습니다. 또한 $PA$의 언어에서 표준적 자연수 모형에서 참인 문장과 비표준적 자연수모형에서 참인 문장들은 서로 같기 때문에 비표준적인 자연수모형을 토대로 무언가 참으로 만든 문장이 있다면 표준적 자연수모형에서도 참이게 됩니다.