Loading [MathJax]/jax/output/HTML-CSS/jax.js



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



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



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


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



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



1.x,y,z ((x+y)+z=x+(y+z))

2.x,y (x+y=y+x)

3.x,y,z ((xy)z=x(yz))

4.x,y (xy=yx)

5.x,y,z (x(y+z)=(xy)+(xz))

6.x (x+0=xx0=0)

7.x (x1=x)

8.x,y,z (x<yy<zx<z)

9.x (¬(x<x))

10.x,y (x<yx=yy<x)

11.x,y,z (x<yx+z<y+z)

12.x,y,z (0<zx<yxz<yz)

13.x,y (x<yz (x+z=y))

14.0<1x (x>0x1)

15.x (x0)


위의 문장들의 집합을 PA라고 합시다. 페아노 공리계의 언어 LPA의 비논리상항에는 0,1,+,,<가 있습니다. xyx<yx=y의 줄임말입니다.


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


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

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


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

Posted by 괴델
,