불완전성 정리

• 관련 항목 : 수학 관련 정보, 논리학 관련 정보

Incompleteness Theorems
쿠르트 괴델이 20세기 초반에 증명한 정리, 그리고 가장 이상적이면서도 완벽한 수학적 기호로 이루어진 이상언어를 만들려는 빈 학파의 노력을 물거품으로 만든 결정타 불확정성과는 다르다.
일부 책에서는 "결정 불가능 정리"라고도 나오는데 불완전성 정리가 맞다.

1 정리

이 정리는 다음의 두 명제로 이루어져 있다.

정리1. 자연수의 사칙연산을 포함하는 어떠한 공리계(즉 페아노 공리계를 포함하는 모든 공리계)도 무모순인 동시에 완전할 수 없다. 어떤 체계가 무모순이라면, 그 체계에서는 참이면서도 증명할 수 없는 명제가 존재한다. 정리2. 자연수의 사칙연산을 포함하는 어떠한 공리계가 무모순일 경우, 그 공리계는 자기 자신의 무모순에 대한 정리를 포함할 수 없다.

'완전하다'는 것은 메타논리학 용어로서, 어떤 형식체계의 귀결이면서 증명 불가능한 명제가 있으면 그 형식체계는 불완전하고 반대로 그 체계의 모든 귀결이 증명가능하다면 완전한 것이다.

즉 불완전성 정리는 자연수의 사칙연산을 포함한 어떠한 공리계에 대해서

• 첫째, 그 공리계 내부의 자료만으론 기계적인 유한한 절차로 참, 거짓을 결정/증명할 수 없는 명제가 반드시 있다. 그렇지 않으면 그 공리계에는 모순이 있다.
• 둘째, 공리계 스스로 자신의 무모순성을 증명할 수 있다면, 그 공리계 내부에 모순이 있다.

라는 것으로 수학적으로는 모든 문제를 풀어내는 일반적이고 기계적인 절차란 있을 수 없다는 것을 암시한다. 간단히 말해서 모든 무모순인 수학의 공리계에는 참이지만 증명할 수 없는 명제가 반드시 하나 이상 포함하며, 스스로 무모순이라는걸 증명할 수도 없다.

논리학의 완전성 정리와 수학에서의 불완전성 정리를 함께 기억하는 사람들이 많은데, 괴델은 완전성 정리를 1929년, 23세 때 제출한 박사논문에서 증명했고, 불완정성 정리는 2년 후 25세때 증명하였다. 참고로 괴델은 대학교에서는 물리학을 전공하였다. 덧붙여, 완전성 정리에 의해서 1차 논리은 반드시 완전한 형식체계이다.

여기까지만 보면 괴델 혼자서 다 해결한 것 같지만, 완전성 정리 및 불완전성 정리의 밑밥은 겐첸이 다 깔아 놨었다. 문제는 겐첸은 힐베르트쪽에 붙어 불완전성보다 완전성을 증명하는데 초점을 두고 있었다. 사람은 그래서 줄을 잘서야 한다 겐첸은 나름대로의 성과를 내서 결국 사칙연산 체계의 무모순성을 증명을 하긴 했다. 하지만, 사칙연산 체계를 넘어섰기 때문에, 공리계 스스로 무모순을 증명한게 아니라 큰 의미를 갖지 못한 것일 뿐이다. 다만, 그 사칙연산 체계를 넘어선 부분이 매우 작기 때문에 Bernays 의 경우 처음 겐첸의 증명을 보고 정말 무모순성이 증명된 줄 알았다고 한다. 그리고, 겐첸의 증명은 그 이상으로 많은 것을 포함하고 있었기 때문에 오늘날 증명이론에서도 중요하게 취급되고 있다.

괴델은 겐첸의 연구로 부터 완정성 정리와 불완정성 정리라는 가장 돋보이는 두가지 정리만 가져간 것이라 보면 된다.

완전성 정리와 불완전성 정리는 일반 스탠다드 classical logic 뿐 아니라, intuitionistic logic, minimal logic 등의 논스탠다드 논리체계에도 적용된다. 이 두가지뿐 아니라, 증명과정중 사용한 primitive recursive function 은 컴퓨터 과학을 탄생시키는 계기가 되기도 하였다. 하지만, 괴델은 이것을 실제 계산기와 같은 기계쪽에 응용할 생각은 하지 않았고 후에 튜링이 primitive recursive function 을 보다 기계친화적인 튜링 기계로 바꾸어 표현하면서 컴퓨터의 아버지라는 이름은 튜링이 가져가게 되었다. 후에 클레이니가 여기에 mu-operator 를 추가하여 class of recursive functions 으로 진화시킨다. 그외에도 lambda calculus, unlimited register machine(URM), while-programming 등과 같은 여러가지 다른 공리계들이 존재한다. 서로 다른 수학자들에게서 독립적으로 서로 다른 방식으로 표현된 공리체계인데도 모두 같은 구조이다.

증명에 대한 기계적인 절차를 제공할 수 있는 체계도 있다. 문장 논리에서는 반드시 그 논리 체계의 어떤 문장이라도 그 문장의 타당성(논리적으로 참)에 대한 검사할 수 있는 방법이 있으며(진리표 방법), 1차 술어 논리에서는 그 문장이 타당하다면 반드시 그것을 도출할 수 있는 방법(증명)이 존재한다.(귀류법을 응용한 방법이다.) 그리고 이 방법을 통해서 그 논리 체계가 완전함을 밝힐 수도 있다고 한다.(이것 역시 위에 나온 논리학의 완전성 정리로 괴델이 증명하였다.) 핵심은 수학의 경우에는 무모순하다는 것에 대한 증명을 그 체계 자체에서 증명될 수 없다는 것이다. 그보다 상위 체계를 동원한다면 가능할 수 있는 것. 게르하르트 겐첸은 유한한 기계적 절차가 아닌 초한귀납법이라는 방법을 동원해서 수체계의 무모순성 증명을 증명하기도 했다.

그냥 관련된 이야기를 공부하고 있으면 세상엔 천재가 있음을 확인하게 된다.

읽어보면 좋은 책으로 <괴델, 에셔, 바흐>, <불완전성> 등이 있다. 단, <괴델, 에셔, 바흐>의 한국어 번역본의 퀄리티는 악명이 높다고 하니(..) 유의하자.

2 '참'과 '증명가능'과 '귀결'

비전공자는 '참', '증명 가능', '증명 불가능', '독립성', '귀결' 등에 대하여 오해하기 쉽다.

불완전성 정리에서 말하는 '참이라고도 거짓이라고도 증명할 수 없는 명제'는 증명도 반증도 불가능하므로 참으로 간주하든 거짓으로 간주하든 자유다. 단 그 명제가 철학적 혹은 현실적으로 타당한가에 달려있다. 물론 타당성을 고려하지 않고 임의 명제(공리)를 채택할 수 있지만 그런 경우는 개인의 선택에 국한되고 사실상 현실에 맞게 합리적으로 명제를 채택한다.

우선 수리논리학, 정확하게 말하자면 메타논리학(metalogic)에서의 주요개념들을 설명하도록 하겠다.

먼저, φ가 명제의 집합 Γ의 귀결(logical consequence)이라는 것은 명제의 집합 Γ의 모든 명제를 만족시키는 모든 모델에서는 φ도 만족된다는 것을 의미한다. 즉 Γ의 모든 원소들이 참이면서 φ가 거짓일 수 없다는 뜻이다. 또한 φ가 명제의 집합 Γ로부터 증명가능하다는 것은 Γ의 명제를 이용하는 기계적이고 유한한 절차만으로 φ를 산출할 수 있다는 것을 의미한다. 여기서 Γ 자체는 무한히 많은 명제들의 집합이라도, φ를 산출하는 데 실제로 사용된 Γ의 명제는 유한한 수이어야 한다.

그리고, 일차술어논리에 관한 세 가지 정리가 있다. 먼저 compactness theorem은 위상수학의 compact 개념을 적용한 것으로, φ가 명제의 집합 Γ의 귀결이면, 명제들의 유한집합 Γ'이 존재해서 "Γ'의 명제는 Γ의 명제이고, 즉 Γ'가 Γ에 포함되고, φ가 Γ'의 귀결이다" 가 성립한다는 것이다.

다음으로 completeness theorem(완전성 정리)과 soundness theorem(건전성 정리)에 의하여, φ가 명제의 집합 Γ의 귀결이라는 것과 φ가 명제의 집합 Γ로부터 증명가능하다는 것은 동치이다.

또한, 제1불완전성 정리는 '참인 명제이지만, 그 긍정이 증명가능하지 않고 부정이 증명가능하지 않은 그런 명제가 있다' 쪽에 가깝다. 그리고 명제의 집합 Γ으로부터 φ도 notφ도 증명가능하지 않으면 φ는 Γ에 독립적이다고 말한다. 여기서 '참이지만 증명가능하지 않다'는 무슨 뜻인가? 이는 이렇게 생각할 수 있다. 아래에서 간략히 제시되겠지만 괴델의 아이디어는 증명가능성을 정수론의 개념으로 convert하는 것이다. 이는 이론체계 바깥에서 이루어지는 일이다. 이것이 잘 들여다보이는 바깥에서 볼 때, 그 convert 과정상 참일 수밖에 없는 문장이 있는데, 그것을 안에서 보면, 즉 그 이론체계 자체만으로는 긍정의 증명도 부정의 증명도 불가능하다는 것이다.

따라서, 위에서 [ ]로 묶어 예시로 든 첫 번째 문단에서 '불완전성 정리의 조건을 만족하는 어떤 공리계에 대해서도 그에 독립인 명제가 존재한다'고 한 부분은 맞지만, 그렇다고 해서 참과 거짓을 엿장수 마음대로 정의할 수 있다는 것은 아니다. 바로 위에서 언급한 증명 과정상의 논의 외에도 수학과 수리철학 등에서의 여러 가지 복잡한 논의가 '참'에 얽혀 있다.

[ ]로 묶어 예시로 든 두 번째 문단에서 참과 증명가능을 구분하는 부분은 맞지만, 참과 귀결을 구분하지 않고 있는 부분은 맞지 않다. 일차술어논리에서 귀결과 증명가능은 동치이므로, 앞뒤가 맞지 않게 되기 때문이다.

정리하면, 참≠귀결=증명가능 이고, 괴델의 불완전성 정리는 어떤 공리계가 특정한 조건을 만족시키기만 하면, 명제 G가 존재해서 괴델의 불완전성 정리의 증명 과정에 의해 G가 참이라는 것을 알 수 있으면서 G의 긍정과 부정 어느 쪽도 그 공리계 내에서 증명가능하지 않다는 것이다. 괴델 이전에는 참과 증명가능을 잘 구분하지 않았기에 공리계를 적절하게 만들어 주면 참=증명가능 이고 긍정과 부정 한쪽만이 증명이 가능하지 않을까 생각하기도 했었는데(힐베르트 등) 괴델의 불완전성 정리 이후 그럴 수는 없고 참과 증명가능은 다르다는 것이 제기된 것이다.

연속체 가설 등의 명제들은 그 명제의 긍정과 부정 어느 쪽도 흔히 사용되는 공리계로부터 증명가능하지 않은 명제들이다.

3 증명

구체적인 증명 없이 논리 구조와 아이디어만을 다룬다.

괴델의 첫 번째 정리를 증명하기 위해서는 '명제'를 숫자, 즉 자연수로 표현하는 약을 빤것 같은 굉장히 독특하고 기발한 방법을 사용했다. 이 방법(알고리즘)은 괴델의 이름을 따서 Goedelization 괴델화 이라 칭하기도 한다. 예를 들어,

')'→1,
'('→2,
'0'→3,
'1'→4,
'+'→5,
'='→6,...

이런 식으로 바꾸는 일반적인 법칙을 제시하면 모든 (계산)명제는 숫자로 바꿀 수 있다. 예를 들어 방금 제시한 법칙으로 '1+0=1'을 쓰면 45364이란 숫자로 변한다.

엄밀히 따지자면 이렇게 했을 경우 10 이상의 숫자에 대응할 수가 없기 때문에 실제로는 저렇게 해당하는 숫자를 나열하지는 않고 각각 2, 3, 5, 7...으로 소수의 순서를 정한 다음 각각의 수를 순서대로 각 소수의 지수로 놓는다. 이렇게 하면 1+0=1이라는 명제의 괴델 수는 837134518374000이 된다.(2^4 × 3^5 × 5^3 × 7^6 × 11^4) 본문의 예는 이해를 쉽기 위해 든 간단한 아이디어니까 대충 이해하자. 여튼 이 숫자를 괴델수Godel Number라고 하고, 괴델수는 당연히 원래의 명제와 일대일대응된다. 이 방법을 응용하면, 명제와 명제와의 관계도 결국 '수와 수의 관계(연산)'가 되어 다시 숫자로 바꿀 수 있다(!)

불완정성 정리는 '참이면서 증명불가능한 명제가 있다'는 것을 증명하고, '참이면서 증명불가능한 명제'와 (가정한)'모순이 없이 스스로를 증명할 수 있는 이론체계'와의 관계를 (복잡하지만) 이용해서 무모순성을 스스로 증명할 수 없다는 것을 증명한 것이다.

'참이면서 증명불가능한 명제가 있다'는 것을 증명한 첫번째 괴델의 정리는 다음의 식을 던져놓는다.

(∀x)~Dem(x, (sub(n, k, n))
이게 뭐야.
뭐긴 뭐야 니가 이해 못하는 식이지
그런 말을 하는 너도 이해 못하잖아

'Dem(x, y)'란 '괴델수가 y인 명제의 증명은 괴델수가 x이다'는 뜻이며, 'sub(n, k, n)'은 '괴델수가 n인 식의 변항 중에서 괴델수가 k인 변항 전부에 n의 이름을 대입한 식의 괴델수'라는 뜻이다. 즉 'Dem(x, y)'는 식이지만 'sub(n, k, n)'은 식이 아닌 수를 지시하는 표현이다. 이 식은 결국 자기 자신에 대해 언급하는 명제이므로 '이 문장은 증명불가능하다.'를 뜻한다. 즉, "괴델수가 몇인 명제이든 이 명제를 증명할 수 없다"를 형식문으로 치환한 것.

그런데, 이 문장은 거짓이거나, 참이거나, 거짓 혹은 참이지만 증명 가능하지 않은 문장이다. 그 이유는,

A. 문장이 거짓이라면 '이 명제는 증명 가능하지 않다'라는 증명이 가능한 문제이고, 그렇다면 '이 명제는 증명 가능하지 않다'가 증명 가능한 것이 되므로 증명이 가능하지 않다는 전제와 모순이 발생한다.
B. 문장이 참이라면 '이 명제는 증명 가능하지 않다'는 증명 가능하지 않은 문제라는 것을 증명하였으므로 증명 가능하지 않다는 전제와 모순이 된다.
C. 문장이 거짓이지만 증명 가능하지 않다고 한다면 '이 명제는 증명 가능하지 않다'는 증명 가능한 문제이나 증명할 수가 없다는 모순으로 가득한 괴상한 말이 되므로 해당되지 않는다.
D. 문장이 참이지만 증명 가능하지 않다고 한다면, B와 같은논리로 모순이 된다.

이걸 아주 쉽게 말하자면,
1. "이 명제는 증명가능하지 않다."라는 명제는 귀류법으로 들쑤셔본 결과 모순(패러독스)이다.
2. "이 명제는 증명가능하지 않다."라는 명제를 적절하게 자연수로 바꿀 수 있다.
3. 따라서 "이 명제는 증명가능하지 않다."라는 명제를 자연수로 바꿔서 끼워넣으면 사칙연산(논리)에 따라 거짓말쟁이의 역설이 일어나 공리계 내부에서 모순이 생긴다는 것이다.

불완전성 정리에 사용된 거짓말쟁이의 역설은 귀류법에 불과한데, 여기에 너무 치중해서 불완전성 정리의 핵심이자 그것이 기발한 이유인 증명이란 '객체'를 사칙연산 체계로 코딩하는 것, 그리고 거기서 computability를 이용하는 것을 간과하는 경우가 있다. 사실 불완전성 정리에서 사용된 귀류법 자체는 수학 증명에서 매우 흔히 사용되는 방법이라, 그다지 신기할것도 없다.

두번째 괴델의 정리는추가바람

괴델은 당시 w-consistency 을 전제하고 증명했는데, 후에 Rosser 가 이 조건 없이 증명을 해보여, 괴델-로서 정리라고도 한다.

영어에 거부감이 없는 위키러라면 이곳을 참고하는 것도 괴델의 정리를 이해하는데 도움이 될 것이다.

4 예시

• 집합론 : ZFC에서 선택공리(Axiom of Choice)자신과 이를 이용해 증명한 정리들은 무모순하지만 다른 공리를 이용해서 참인지 거짓인지 증명할 수 없다.

• 연속체 가설 : 모든 무한집합의 원소수(기수)는 [math] \aleph_n [/math]꼴로 표현 할 수 있다 여기서 [math] 2 ^{\aleph_0} = \aleph_1 [/math] 이 성립하겠느냐는 것이 연속체 가설이고, 일반화된 것은 [math] 2^{\aleph_N} = \aleph_{N+1} [/math] 이 성립하지 않을까 하는 일반연속체가설. 좀더 자세한 것은 연속체 가설과 초한기수 문서 참조.

• Word problem for groups

• torsion-free, total separable group 은 free 인가

• 네이쳐 기사 번역 및 설명(불완전성 정리가 적용되는 물리학 문제. 설명 추가바람)

5 반응과 이용

• 이 정리 하나로 힐베르트와 프레게가 만들어나가던 "완전한 수학체계에 대한 꿈"이 박살났다. 시무룩
• 괴델이 이것을 증명하기 20여년 전부터 힐베르트는 "모든 명제가 공리계로부터 증명 가능한 완전한 수학체계"라는 꿈을 가지고 있었다. 러셀의 역설 때문에 한번 막힐뻔했으나 그래도 힐베르트는 이것을 위해 수학의 난제들을 하나하나 정리했고 프레게는 "수"와 "군"에 관한, 공리계의 기초를 닦아나가며 꿈을 키웠으나, 이 완전한 수학체계라는 것이 보시다시피 불완전성 제 1 정리와 완전히 반대되는 것이다. 즉 힐베르트가 꿈꾸던 수학체계는 완전히 박살나버렸다. 그래도 힐베르트 및 수학자들은 "그래도 저런 건 극소수고 중요한 정리들은 안 그럴거야"하면서 간신히 버텼으나 1963년에 힐베르트 자신이 가장 중요한 23개 수학문제 중에 제 1로 올려놓은 연속체 가설이 여기 포함됨이 증명되어 결국 완전한 수학체계의 꿈은 박살나버렸다.
• 당시에는 증명이 난해하다기보다는, 논리체계를 '이용하는' 수학이 그런 논리체계 자체를 수학적 대상으로 환원하여 연구한다는 부분을 잘 이해하지 못하여 대부분의 비수학자들은 그저 논리와 이성으로 이 세상을 완전히 설명할 수는 없다는 정도로 받아들일 수도 있을 것 같다, 는 식으로 이해했고, 지금도 비전공자들은 막연히 그정도로만 이해한다.
• 철학자들 역시 예외가 아니어서, 철학적으로는 우리가 진리에 결코 도달할 수 없다는 뜻으로 해석되기도 한다. 몽테뉴, 니체가 했던 주장의 개정판인 셈이다. 이것도 물론 불완전성을 이해해서 확장했다기보다는 그냥 좋은 소재(같은 예로는 상대성이론, 양자역학)를 물었을 뿐이다. 불완정성 정리를 이용해서 개드립을 치던 신좌파 철학자들은 나중에 앨런 소칼에게 걸려서 박살이 났다. 원래 진리에 결코 도달할 수 없다는 주장의 기원은 소피스트가 자기네끼리 투닥투닥하던 시절까지 거슬러 올라간다.
• 문학에서는 어쨌거나 뜻의 난해함과 불완전성이라는 단어가 주는 포스트모던적인 강렬함 덕분에 억지를 진실로 진실을 억지로도 재정리 할 수 있는 논리체계라고 오해를 받는데, 괴델의 정리는 '참으로 증명된 정리'의 존재를 부정하지도 않고, 참인 명제를 거짓이라고 선언하지도 않는다.
• SF에서 막판반전 혹은 도입부의 소재로 사용된 적이 있고 80년대 후반, 동인 소설팀인 미도리쿠로시로의 시로쿠로미도리란 소설에서 주요 주제로 사용되었으나 반전을 반전으로 덮어 버리는 것을 반복하는 따라가기 어려운 글들이 되어버렸기에 주제로 내세우면 해결안된 글만 가득한 이상한 글이 되어서 대개의 경우 소리소문 없이 파묻혀 버렸다.
• 스즈미야 하루히의 우울 4권에서 언급되었으나 깊게 파들어가면 하나의 실수로 개피본단 것을 알고 슬쩍 쓰고 묻혔다..
• 모순성과 모든 것이 증명된다에 관한 논의는 프레게의 논리학 체계에서 나오는 '러셀의 역설'과 관련된 것 같은데 러셀의 역설은 일반적인 논리 체계에서 적용되지 않는다. 모순에서 모든 것이 증명된다는 것은 중세 때에 발견된 EFQ(Ex Falso Quodlibet, 둔스 스코투스의 정리)로, 이것도 정확히는 '모든 것이 참으로 증명된다'는 의미라고 하는 것이 정확하겠다.
• 조금 더 일찍 나온 불확정성 원리가 주는, 세상은 확률론적으로 이루어져 '참과 동시에 거짓이다'라는 식의 오해가 쓰기 더 편리하기 때문에 더 이상은 등장하지 않을 듯 하다.이상은, 써먹기 편한 말들을 좇아 헤매는 사이비 철학들을 걸러내는 좋은 주제어들일 수도 있다
• 불완전성 정리를 주제로 한 단편 소설을 하나 쓸바에 들개를 훈련시켜 미국 대통령을 암살하는 일이 쉽다는 말도 있다.
• 다만, 일본의 수학 교양소설 '수학 걸 3권 - 괴델의 불완전성 정리'의 내용이 바로 고등학생들이 괴델의 불완전성 정리를 탐구하는 것이다. 그런데 그것이 실제로 일어났습니다 (...)
• 사실 중세 및 근대초기, 오일러-가우스 시절까지의 수학에서는 지금의 고교수학 같이 단순히 주어진 수식의 연산정도만이 관심사였고, 해당 '체계' 및 '시스템 자체'의 엄밀함에 신경쓰기 시작한것은 코시라는 수학자가 등장한 이후부터였다. 그러나 수학의 전체적인 시스템을 엄밀하게 증명하는 과정에서 제대로 좋은 결과를 보여준적은 거의 없다. 갈루아는 5차 이상의 방정식의 해를 구하는 공식은 없다는 결론을 내었고, 측도론에서는 실수공간의 임의의 부분집합의 넓이를 구하는 함수는 존재하지 않음을 보인데 더해서, 바나흐-타르스키 패러독스에서는 선택공리를 이용해 순수하게 자르기와 공간이동만의 방법을 사용해서 실수공간의 임의의 부피를 가진 공 여러개를 모두 같은 부피로 만들 수 있음을 보이기까지 한다.
• 괴델의 불완전성 정리 역시 이 연장선상에서 수학 그 자체의 불완정성을 보인것이다. 현대수학은 매우 확고한 기초를 가진듯 보이지만, 사실 내부사정을 조금 들여다보면 이래저래 '의미적'으로도 위의 바나흐-타르스키 패러독스같은 여러가지 역설이 존재하기때문에 공격받는 부분이 많고, 그외에도 철학적으로 비구성적 오브젝트를 허용한데 대한 입장차이등으로 인하여 공격받는 부분이 많아 '물 바깥에서 보기엔 우아하고 아름답지만, 안에서는 열심히 다리를 허우적대는 백조'와 같은 모양새를 띄고 있다. 괜히 러셀이 '수학의 원리'같은 책을 낸 것이 아니다.
• 골드바흐의 추측과 얽혀서 "어쩌면 골드바흐의 추측도 저 "참이면서도 증명할 수 없는 명제"(참 거짓을 증명 할 수 없는 문제)가 아닐까?" 하는 것을 써먹은 소설 <사람들이 모두 미쳤다고 말한 외로운 수학 천재 이야기>가 있다. 아직까지 증명도 반증도 안되니 참으로 간주하는 것. 페르마의 대정리도 증명되기 전에는 비슷한 의심을 하는 사람들이 있었다.