불완전성 정리
덤프버전 :
1. 개요[편집]
모순이 없는 수학 체계에는 반드시 증명할 수 없는 명제가 있다는 정리이다.
쿠르트 괴델이 1931년에 발표했다. 19세기 해석학(수학)의 발달 및 비유클리드 기하학의 본격적인 등장으로 촉발된 수학 기초론의 대표적인 성과로서, 현대 논리학의 토대인 동시에 20세기 수학 및 철학, 컴퓨터과학 등 많은 분야에 큰 영향을 미쳤다. 참고로, 이 정리에 자극 받은 앨런 튜링이 본인 방식으로 곧이어 논문을 썼었고, 그 논문에 튜링 머신이란 개념이 등장하게 된다.
다른 학문에서의 결정 불가능성 개념으로 베르너 하이젠베르크가 발견한 물리학의 불확정성 원리, 컴퓨터과학에서 앨런 튜링이 증명한 정지 문제, 케네스 애로우가 증명한 경제학의 불가능성 정리, 언어철학에서 뢰벤하임-스콜렘 정리의 함의를 이어 콰인이 제시한 번역 불확정성 논제[1] , 그리고 수리논리학에서 타르스키가 증명한 타르스키의 정의 불가능성 정리가 있다.
참고로, 쿠르트 괴델 본인이 1929년에 증명한 완전성 정리와 혼동하지 말 것.
2. 정리[편집]
불완전성 정리는 "제1 불완전성 정리"와 "제2 불완전성 정리"라는 두 정리를 아우르는 말이다.
페아노 공리계란 우리가 사용하고 있는 자연수에 관한 공리를 말한다. [math(1+1=2)]라는 것도 이를 통해 정의된 것이다. 그런데 이 공리를 포함하는 체계가 모순이 없다면, 참인데 증명할 수 없는 명제가 존재한다는 것이다.제1정리. 페아노 공리계를 포함하는 어떠한 공리계도 무모순인 동시에 완전할 수 없다. 즉 자연수 체계를 포함하는 어떤 체계가 무모순이라면, 그 체계에서는 참이면서도 증명할 수 없는 명제가 적어도 하나 이상 존재한다.
제2정리. 페아노 공리계가 포함된 어떠한 공리계가 무모순일 경우, 그 공리계로부터 그 공리계 자신의 무모순성을 도출할 수 없다.
2.1. 주요 개념[편집]
수리논리학에서 쓰이는 "참", "증명가능성", "귀결" 등의 개념은 자칫 오해하기 쉽다. 오해를 방지하기 위하여 관련 개념을 약술하자면 다음과 같다:
"불완전성 정리"에서 말하는 "완전성(completeness)"이란 "건전성(soundness)"과 대비되는 성질이다.[2] 임의의 형식 체계 [math(P)], 명제 집합 [math(\Gamma)], 그리고 명제 [math(\phi)]에 관하여 이들 개념은 다음과 같이 정의될 수 있다:
이때 "증명가능성"과 "논리적 귀결"은 각각 다음과 같이 정의된다:* [math(P)]의 건전성: [math(P)]에서 [math(\Gamma)]로부터 [math(\phi)]가 증명가능하다면, [math(P)]에서 [math(\phi)]는 [math(\Gamma)]의 논리적 귀결이다.
* [math(P)]가 건전하면 [math(P)]는 무모순적이다.
* [math(P)]의 완전성: [math(P)]에서 [math(\phi)]가 [math(\Gamma)]의 논리적 귀결이라면, [math(\phi)]가 [math(P)]에서 타당하다면, [math(P)]에서 명제 [math(\phi)]는 [math(\Gamma)]로부터 증명가능하다.
명제 논리는 건전하며 완전하다. 더욱이 명제 논리의 경우 임의의 [math(\Gamma)]와 [math(\phi)]에 대하여 [math(\phi)]가 [math(\Gamma)]의 논리적 귀결인지 여부를 유한번 단계 내에 판단할 수 있게끔 해주는 절차가 있으므로 결정가능하다.* [math(P)]에서 [math(\phi)]는 [math(\Gamma)]로부터 증명가능하다 [math(\Leftrightarrow)] [math(\Gamma)]의 원소들 및 [math(P)]의 공리들에 [math(P)]의 도출 규칙을 유한번 적용하여 [math(\phi)]를 얻을 수 있다.
* [math(P)]에서 [math(\phi)]는 [math(\Gamma)]의 논리적 귀결이다 [math(\Leftrightarrow)] [math(P)]에서 [math(\Gamma)]의 모든 원소들이 참인 경우 [math(\phi)]도 반드시 참이다 [math(\Leftrightarrow)] [math(\Gamma)]의 모든 원소들이 참인 임의의 모형에서 [math(\phi)]는 참이다.
1차 술어 논리는 건전한 동시에 완전하지만, 결정가능하지는 않다. 따라서 만약 [math(\phi)]가 [math(\Gamma)]의 논리적 귀결이라면 그 사실은 유한 번 단계 내에 판단할 수 있지만, [math(\phi)]가 [math(\Gamma)]의 논리적 귀결이 아니라면 그럴 수 없다. 1차 술어 논리의 완전성 또한 괴델이 증명한 것이다.
자연수 산술을 가능케 하는 페아노 공리계를 포함하는 형식 체계는 1차 논리보다 강력하다. 괴델의 불완전성 정리는 이런 논리 체계가 완전성을 띠지 않는다는 점을 보여주는 것이다. 곧 설령 참이라 한들 그에 대한 증명도, 그 부정에 대한 증명도 불가능한 문장들이 있다는 것이다. 밑에서도 나오겠지만 연속체 가설을 비롯한 몇몇 명제들이 바로 그 사례다.
3. 증명 아이디어[편집]
아래 증명 아이디어는 어니스트 네이글과 제임스 뉴먼의 고전적인 대중서, 『괴델의 증명』에서 따온 것이다.
3.1. 제1정리[편집]
제1불완전성 정리 증명의 실질적인 첫 단계는 임의의 식을 자연수로 번역하는 절차를 만드는 것이다.[3] 그 방식은 다양하나, 요체는 모든 식 각각에 고유한 자연수를 부여하는 것이다. 이처럼 그 식과 일대일로 대응하는 자연수를 그 식의 괴델수(Godel number)라고 부른다.
산술식 [math(1+0=1)]를 예로 들어보자. 이 식에 등장하는 기호의 유형은 '[math(1)]', '[math(+)]', '[math(0)]', '[math(=)]'로 네 가지다. 이때 각 기호의 유형마다 고유한 자연수를 부여하자. 그 예는 다음과 같다.[4]
[math(\displaystyle\text{괴델 수}=\prod^n_{k=1}P_k^{(k\text{번째로 오는 기호 유형에 상응하는 괴델수})}\quad(\text{단, }P_k\text{는 }k\text{번째 소수}))]
예컨대 [math(1+0=1)]의 첫 자리에 나타나는 '1'은 [math(2^4=16)]으로 번역가능하다. 그리고 이렇게 번역된 각 자연수들을 다 곱함으로써 식 전체를 그 괴델수로 번역할 수 있다. 이를테면 [math(1+0=1)]의 괴델수는 [math(2^4\times3^5\times5^3\times7^6\times11^4=837134518374000)]이 된다.
이처럼 임의의 식에 상응하는 괴델수를 계산해낼 수 있다. 그리고 똑같은 원리에 의거하여 여러 식들의 나열, 이를테면 증명에 해당하는 괴델수 또한 계산하는 것이 가능하다.
이를 토대로 다음과 같은 개념을 정의하자:
- 식 '[math(Dem(x, y))]': '괴델수가 [math(y)]인 명제의 증명은 괴델수가 [math(x)]이다'
- 예. '[math(\exists x Dem(x, y))]':' '괴델수가 [math(y)]인 명제의 증명이 존재한다'
- 함수 [math(sub(n, k, n))]: 괴델수가 [math(n)]인 식의 변항 중 괴델수가 [math(k)]인 변항에 ([math(n)]을 나타내는 기호인) '[math(n)]'을 대입해서 얻은 식의 괴델수[주의]
- 예. 식 '[math(\exists x (x=y))]'의 괴델수가 [math(m)]이라고 하고, '[math(y)]'의 괴델수가[math(j)]라고 하자. [math(sub(m, j, m))]는 '[math(\exists x (x=y))]'에서 '[math(y)]'를 '[math(m)]'으로 교체한 식의 괴델수다.[주의]
변항 '[math(y)]'의 괴델수를 17이라고 가정하라. 이때 식 '[math(\neg ∃xDem(x, sub(y, 17, y)))]'의 의미는 정의상 '괴델수가 [math(sub(y, 17, y))]인 식의 증명은 존재하지 않는다'가 될 것이다.[주의] 이때 '[math(\neg ∃xDem(x, sub(y, 17, y)))]'의 괴델수는 [math(n)]이라 하자. 그렇다면 [math(n)]을 나타내는 기호 '[math(n)]'을 포함하는 다음 식 [math(G)] 또한 생각할 수 있다.
- [math(G)]: '[math(\neg ∃xDem(x, sub(n, 17, n)))]'
- 의미: '괴델수가 [math(sub(n, 17, n))]인 식의 증명은 존재하지 않는다'
이때 [math(G)]의 괴델수를 [math(g)]라고 하자. 그런데 [math(g = sub(n, 17, n))]이다. 왜냐면 가정상 괴델수가 [math(n)]인 식은 '[math(\neg ∃xDem(x, sub(y, 17, y)))]'인데, 정의상 [math(sub(n, 17, n))]은 이 식에서 '[math(y)]'를 '[math(n)]'으로 대체한 식의 괴델수이고, '[math(y)]'를 '[math(n)]'으로 대체한 바로 그 식이 [math(G)]이기 때문이다. 그 [math(G)]의 괴델수가 [math(g)]이므로, 곧 [math(g)]는 [math(sub(n, 17, n))]와 같다.
그러므로 [math(G)]의 의미는 '괴델수가 [math(g)]인 식의 증명은 존재하지 않는다'라고도 볼 수 있다. 그런데 괴델수가 [math(g)]인 식은 바로 [math(G)]다. 따라서 [math(G)]의 의미는 '[math(G)]의 증명은 존재하지 않는다'는 것이다. 먼저 [math(G)]의 증명이 존재한다고 가정해보자. 그러면 명제 [math(G)]는 거짓인데, 이로부터 [math(G)]의 부정의 증명 또한 있음을 보일 수 있다. 하지만 이는 무모순성을 위반한다.[5] 역으로 명제 [math(G)]의 부정에 대한 증명이 존재한다고 가정할 경우에도 무모순성이 위반된다.[6]
즉 대우를 취할 경우, 주어진 증명 체계가 무모순적이라면 [math(G)]와 그 부정 둘 중 어느 것도 증명할 수 없으므로 불완전하다는 점이 도출된다. 그리고 [math(G)]의 의미상 [math(G)]는 참이 된다. 따라서 참이지만 증명할 수 없는 명제가 있다.
3.2. 제2정리[편집]
모순적인 공리계로부터는 어떠한 명제든지 증명할 수 있으므로, 무모순적인 공리계는 증명불가능한 명제가 있는 공리계다. 따라서 '페아노 공리계는 무모순적이다'라는 문장은 괴델수 번역 등을 통해 페아노 공리계 안에서[7] 다음과 같은 형태로 기술될 수 있다.
- '[math(\exists y \neg \exists x Dem(x,y))]'
- 의미: '그 증명에 해당하는 괴델수 [math(x)]가 없는 식의 괴델수 [math(y)]가 존재한다.'
4. 반응 및 영향[편집]
4.1. 수학 및 그 사례[편집]
현대의 표준적 집합론인 ZFC 공리계는 페아노 공리계의 모형을 제공할 뿐 아니라 뭇 수 체계를 포괄한다는 점에서 표준 수학의 '기초'가 된다. 그런데 페아노 공리계를 해석할 수 있다는 그 점으로 인해 ZFC 또한 불완전성 정리에서 피해갈 수 없다. 결국 ZFC를 기초로 삼는 한 참임에도 불구하고 증명할 수 없는 명제가 존재하며, ZFC의 무모순성은 ZFC에서 증명할 수 없다.
관건은 수학적으로 충분히 "흥미로운" 명제 가운데서도 하필이면 증명불가능한 명제가 있느냐는 점. 공교롭게도 힐베르트의 23가지 문제 중 하나로도 꼽혔던 연속체 가설이 ZFC 공리계와 무모순이라는 것을 쿠르트 괴델이, 해당 가설의 부정이 ZFC와 무모순이라는 것을 폴 코언이 증명함으로써 불완전성 정리가 적용되는 흥미로운 사례가 입증되었다. 불행인지 다행인지 힐베르트는 연속체 가설이 무모순이라는 것만 보고 죽었지만...
아래는 그 대표적인 사례들이다.
- 연속체 가설[9] : 모든 무한집합의 원소수(기수)는 [math( \aleph_n )]꼴로 표현 할 수 있다 여기서 [math( 2 ^{\aleph_0} = \aleph_1 )] 이 성립하겠느냐는 것이 연속체 가설이고, 일반화된 것은 [math( 2^{\aleph_N} = \aleph_{N+1} )] 이 성립하지 않을까 하는 일반연속체가설. 좀 더 자세한 것은 연속체 가설과 초한기수 문서 참조.
- Word problem for groups[10]
4.2. 계산 이론[편집]
계산 이론에 의해 불완전성 정리는 자연수론을 포함한 임의의 공리계에 대해서 다음과 같은 함축을 갖는다:
- 그 공리계 내부의 자료만으론 기계적인 유한한 절차로 참, 거짓을 결정/증명할 수 없는 명제가 반드시 있다. 그렇지 않으면 그 공리계에는 모순이 있다.
핵심은 수학의 경우에는 무모순하다는 것에 대한 증명을 그 체계 자체에서 증명될 수 없다는 것이다. 그보다 상위 체계를 동원한다면 가능할 수 있는 것. 게르하르트 겐첸은 유한한 기계적 절차가 아닌 초한귀납법이라는 방법을 동원해서 수체계의 무모순성 증명을 증명하기도 했다.
증명과정 중 사용한 원시 재귀함수는 컴퓨터과학을 탄생시키는 계기가 되기도 하였다. 하지만, 괴델은 이것을 실제 계산기와 같은 기계 쪽에 응용할 생각은 하지 않았고 후에 앨런 튜링이 원시 재귀함수를 보다 기계친화적인 튜링 머신으로 바꾸어 표현하면서 컴퓨터의 아버지라는 이름은 튜링이 가져가게 되었다.
그리고 위 조건을 만족시키는 다양한 기계적인 유한한 절차들마다[14] 그에 해당하는 튜링 머신이 있으며 그 역 또한 성립함이 증명되었다. 이를 보다 확장하여 모든 계산가능한 함수마다 그에 상응하는 튜링 머신이 존재한다는 주장이 유명한 처치-튜링 명제이다.[15]
4.3. 철학[편집]
불완전성 정리에 대한 잘못된 해석 한 가지는 "참도 거짓도 아닌 수학적 명제가 있다"는 것이 불완전성 정리를 통해 증명되었다는 것이다. 이 해석이 잘못된 이유는 참임에도 불구하고 증명이 불가능한 명제 [math(G)]가 있다는 것이 바로 제1정리이기 때문이다. 참도 거짓도 아닌 명제, 참이면서 동시에 거짓인 명제 등을 인정하는 비고전 논리학이 존재하는 것은 분명하지만, 이는 불완전성 정리로부터 곧장 따라나오는 것이 결코 아니다.수학 기초론에 관한 지난 수십 년 동안의 연구 성과는 비단 그 자체로 흥미로울 뿐 아니라, 수학의 본성 같은 전통적인 철학적 문제들에 시사하는 바에 있어서도 흥미롭다고 봅니다.[16]
--쿠르트 괴델, 1951년 Gibbs 강연 '수학 기초론의 몇몇 기본적 정리들과 그 함축' 中
수학철학에서 쿠르트 괴델 본인은 오히려 플라톤의 견해를 그대로 받아들였다고 해도 과언이 아닐 정도의 강경한 실재론을 옹호했다. 즉 우리가 원리적으로 알 수 있건 없건 수학적 명제의 참거짓은 객관적으로 존재한다는 것. 괴델은 오히려 1951년 Gibbs 강연에서 (특정 조건이 만족된다는 가정 하에서) 불완전성 정리는 오히려 수학적 참이 객관적이라는 근거가 된다는 논변을 제안하기도 했다.
제2불완전성 정리가 확실히 직격한 수학 기초론은 다비트 힐베르트의 이른바 '힐베르트 프로그램'이다. 왜냐면 힐베르트 프로그램의 핵심은 형식화된 수학 이론의 무모순성을 유한한 절차에 의거하여 증명하려는데 있었기 때문이다. 괴델은 힐베르트학파 수학자들의 맹렬한 반론을 예상하여 이에 대응하기 위한 후속 논문을 불완전성 정리를 발표하는 논문에서 이미 예고했으나, 힐베르트 및 그 제자들은 불완전성 정리에 아무런 반론을 제기하지 않았으며, 이 때문에 예고했던 후속 논문은 나오지 않았다. 힐베르트는 그 대신 '유한한 절차'에 대한 제한조건을 일부 포기하고 초한귀납법을 받아들임으로써 불완전성 정리의 장벽을 우회하려고 시도했으며, 이러한 무모순성 증명은 힐베르트의 조수였던 게르하르트 겐첸에 의해 달성되었다. 힐베르트 학파 측에서 '유한한 절차'라는 말을 엄밀하게 정의한 적이 없기에 겐첸의 무모순성 증명이 갖는 의의에 대해서는 철학사적 논쟁이 분분하지만, 당대의 많은 논리학자들은 초한귀납법을 통한 증명으로는 힐베르트 프로그램의 철학적 목표를 달성할 수 없다고 진단했다.
고틀로프 프레게와 버트런드 러셀, 그리고 논리 실증주의자들이 개진했던 논리주의 프로그램 또한 불완전성 정리 등장 이후 대대적인 수정이 불가피하게 되었다. 루돌프 카르납은 괴델 본인이 제안한 철학적 비판에 맞서 1930년대 이후 많은 이론적 수정을 가해야했으며, 1980년대 이후 진행되는 신논리주의 프로그램은 아예 고전적 논리주의의 여러 전제들을 포기하고 진행중이다.
심리철학에서 불완전성 정리가 언급되는 유명한 떡밥은 다음과 같다:
괴델 자신 또한 그 가능성을 지나가면서 언급한 적은 있으나, 현대에도 이런 떡밥을 꾸준히 대중적으로 미는 학자로는 로저 펜로즈가 있다.불완전성 정리에 따르면 기계적인 절차에 근거하여 참을 보일 수 없는 명제가 있다. 그런데 우리 인간은 그 참을 보일 수 있다. 따라서 인간의 마음은 계산 기계가 아니다.
5. 대중적 인식[편집]
- 당시에는 증명이 난해하다기보다는, 논리체계를 '이용하는' 수학이 그런 논리체계 자체를 수학적 대상으로 환원하여 연구한다는 부분을 잘 이해하지 못하여 대부분의 비수학자들은 그저 논리와 이성으로 이 세상을 완전히 설명할 수는 없다는 정도로 받아들일 수도 있을 것 같다, 는 식으로 이해했고, 지금도 비전공자들은 막연히 그 정도로만 이해한다.[17]
- 몇몇 철학자들은 '우리가 진리에 결코 도달할 수 없다'는 뜻으로 해석하기도 한다. 미셸 드 몽테뉴, 프리드리히 니체가 했던 주장의 개정판인 셈인데, 물론 잘못된 해석이다. 수학의 위치를 생각해 보았을 때 철학적으로 중요한 기획 하나가 실패를 겪었다는 것은 사실이지만, 그 이외의 영역에서까지 이를 확장하는 것은 주의해야 한다. 대부분 이런 주장들은, 불완전성 정리를 제대로 이해해서 확장했다기보다는 그냥 좋은 소재(같은 예로는 상대성 이론, 양자역학)를 물었을 뿐이다. 불완전성 정리를 이용해서 개드립을 치던 사람들은 나중에 앨런 소칼에게 걸려서 박살이 났다. 원래 진리에 결코 도달할 수 없다는 주장의 기원은 소피스트가 자기네끼리 투닥투닥하던 시절까지 거슬러 올라간다. 진리에 결코 도달할 수 없다는 것이 아니라 진짜 진리에 도달한다해도 그게 진리가 맞는지 증명할 수 없을 수도 있다고 이해하면 빠를 것이다.
- 문학에서는 어쨌거나 뜻의 난해함과 불완전성이라는 단어가 주는 포스트모던적인 강렬함 덕분에 억지를 진실로 진실을 억지로도 재정리 할 수 있는 논리체계라고 오해를 받는데, 괴델의 정리는 '참으로 증명된 정리'의 존재를 부정하지도 않고, 참인 명제를 거짓이라고 선언하지도 않는다.
- 조금 더 일찍 나온 불확정성 원리가 주는, 세상은 확률론적으로 이루어져 '참과 동시에 거짓이다'라는 식의 오해가 쓰기 더 편리하기 때문에 더 이상은 등장하지 않을 듯하다.
- 사실 오일러-가우스 시절까지의 수학에서는 단순히 주어진 수식의 연산 정도만이 관심사였고, 해당 '체계' 및 '시스템 자체'의 엄밀함에 신경쓰기 시작한 것은 코시라는 수학자가 등장한 이후부터였다.[18] 희한하게도 수학의 전체적인 시스템을 엄밀하게 증명하는 과정을 보면 뭔가가 안 된다는 결론들이 많았다. 갈루아는 5차 이상의 방정식의 해를 구하는 공식은 없다는 결론을 내었고, 측도론에서는 3차원 이상 실수공간의 임의의 부분집합의 넓이를 구하는 함수는 존재하지 않음[19] 을 보인데 더해서[20] , 바나흐-타르스키 역설에서는 선택공리[21] 를 이용해 순수하게 집합의 분할과 공간이동[22] 만의 방법을 사용해서 3차원 실수공간의 서로 다른 부피를 가진 공 2개의 조각들이 모두 서로 대응함을 보여준다.[23] 위에서 언급한 wording problem도 그 한 예시로 볼 수 있겠다. 그래도 대수학에서의 다양한 분류(classification) 문제들이 풀렸고 측도론을 기반으로 해석학이 함수해석학 등 세부 분야를 통하여 눈부신 발전을 이루어 냈으며 위상수학 등을 통하여 호모토피, 호몰로지, 더 나아가 대수기하학 등이 융성한 것을 보면 이러한 방법론이 꽤 유용하면서도 아직 할 일이 많다는
즉 돈줄이 아직 안 끊겼다는것을 짐작할 수 있을 것이다. - 괴델의 불완전성 정리 역시 이 연장선상에서 수학 그 자체의 불완전성을 보인 것이다. 현대수학은 매우 확고한 기초를 가진듯 보이지만, 사실 내부사정을 조금 들여다보면 이래저래 '의미적'으로도 위의 바나흐-타르스키 역설 같은 여러 가지 역설이 존재하기 때문에 공격받는 부분이 많고, 그 외에도 철학적으로 비구성적 오브젝트를 허용한데 대한 입장차이 등으로 인하여 공격받는 부분이 많아 '물 바깥에서 보기엔 우아하고 아름답지만, 안에서는 열심히 다리를 허우적대는 백조'와 같은 모양새를 띠고 있다. 괜히 러셀이 '수학의 원리'같은 책을 낸 것이 아니다.
- 골드바흐 추측과 얽혀서 "어쩌면 골드바흐의 추측도 저 "참이면서도 증명할 수 없는 명제"(참 거짓을 증명할 수 없는 문제)가 아닐까?" 하는 것을 써먹은 소설 <사람들이 모두 미쳤다고 말한 외로운 수학 천재 이야기>가 있다. 아직까지 증명도 반증도 안 되니 참으로 간주하는 것. 페르마의 마지막 정리도 증명되기 전에는 비슷한 의심을 하는 사람들이 있었다.
- 읽어보면 좋은 책으로 <괴델, 에셔, 바흐>, <불완전성> 등이 있다. 참고로 <괴델, 에셔, 바흐>는 구판 한국어 번역본의 퀄리티는 악명이 높았지만, 2017년에 나온 개정판은 역자가 바뀌면서 번역의 질이 압도적으로 높아졌다.