괴델과 그의 불완전성 정리

 

김병한 (연세대학교)

 

 

 

타임지가 선정한 20세기 가장 영향력 있던 인물 100명중엔 2명의 수학자가 포함되어 있다. 불안정성 정리로 유명한 괴델(Kurt Gödel)과, 현대 컴퓨터의 이론적 토대를 세운 튜링(Alan Turing)이 그들인데, 두 사람 모두 수학의 분야 중 수리논리학에서 업적을 이루었다. 물리학자들이 그들의 대표자격인 아인슈타인을 통해 물리학의 대중화를 유도하고, 저변을 확대하는 것은 주지의 사실이다. 작년 2005년만 하더라도 상대성 원리 발견 100주년이라 하여 한국에서도 여러 대중적 행사와 전람회 등이 있었던 것을 필자도 기억한다. 하지만 지난 한 세기의 수학을 대표한다고 할 수 있는 (적어도 대중들에게 그렇게 소개할 수 있는 소수의 수학자중 하나인) 괴델은 일부 수학자들조차도 생소하게 느끼는 것이 현실이다. 부끄러운 얘기이나, 한국에선 그것이 좀 더 심하여 괴델, 튜링의 전공분야인 수리논리학을 전공하는 한국학자는 그야말로 두, 세 명이 전부라 할 수 있겠다. 올 해는 사실 괴델 탄생 100주년을 맞는 해이다. 이를 기념하여 미국수학회보(AMS Notices) 4월호 전면이 괴델특집으로 꾸며진 것과 비교할 때, 국내의 괴델에 대한 이해와 관심은 수학자들 사이에서도 분발을 요구한다. 이 글도 그 일환으로 기고하였다. 이 글을 통해 그의 삶과 학문적 업적에 대해 짧게나마 정리해 보려한다.

괴델은 1906년 4월, 당시 오스트리아 브르노(현 체코령)의 중상층 가정에서 태어나, 그곳에서 어린 시절을 보냈다. 모든 과목에 최고성적을 내는 우수하고 영민한 학생이었는데, 다만 류머티즘으로 인한 발열성 질병으로 자주 결석하곤 하였다. 이는, 완치되었다는 의사의 설명에도 불구하고, 일생에 거쳐 지나친 건강 염려증으로 발전하는 계기가 되었다고 한다. 1924년엔 오스트리아의 비엔나 대학에 입학하여, 그 곳에서 10수 년 간 학자로 성장하며 그의 생애 최대 업적들을 이루게 된다. 대학에서 물리학을 시작으로 철학, 수학을 공부하였는데, 지도교수 한(Hans Hahn)을 만난이후 그의 관심은 수리논리학에 집중된다.

 

한은 원래 해석학자였으나 말년에는 수리논리학에 관심을 보여, 당시 논리학을 공부하는 사람은 그에게서 학위를 해야 했다. 한은 비엔나 서클(Vienna Circle)의 주요 창시자 중 한 명으로도 유명하다. 카르납, 포퍼, 비트겐슈타인 등 당시 최고 철학자들이 주 구성원이었던 비엔나 서클은 특정의 협의체를 구성한 조직이 아니었다. 비엔나에 근거를 둔 다양한 학자들이 정기적, 또는 부정기적으로 만나 담소를 나누며 철학, 논리학, 심리학 등의 주요주제에 대해 토론하고 논의를 진전시킨, 학문연구의 장이었다. 그러나 그 내용은 매우 심도 있어, 학문진보의 기지 역할을 하였다. 특히 1920-30년대 당시 매우 역동적으로 발전하는 수리논리학은 그들이 크게 관심 갖던 분야 중 하나였다.

여기서 당시 수리논리학의 탄생과 발달을 잠시 살펴보자. 수리논리학은 수학의 기초를 건설하는 집합론, 기호논리학 등을 포괄하는 학문이란 의미에서 수학기초론으로도 불린다. 18, 19세기 거듭된 수학의 성과는 엄밀성이 미처 확보되지 못한 상태에서 얻어졌다. 예를 들어 수열의 수렴성, 함수 연속성과 미분 가능성 등의 엄밀한 정의가 확립되지 않은 가운데 많은 결과들이 발견되었고, 때로는 모순되거나, 잘못 된 결과가 여과 없이 받아들여졌다. 이런 난점들을 타계하고 수학의 기초를 건설하는 도구로 칸토르가 19세기 말 우연한 계기로 확립한 집합론이, 초기 일부의 거부에도 불구하고, 점차 받아들여진다.

 

칸토르는 집합론의 논법으로, 당시까지 미지의 영역으로 터부시 돼왔던 무한 개념을 엄밀히 다룰 수 있었다. 특히 무한집합 사이의 ‘크기’ (또는 기수, cardinality)를 일대일 대응으로 논하는데, 이는 매우 획기적인 생각이었다. 예를 들어 자연수 집합은 유리수 집합의 부분집합임에도, 서로 간에 일대일 대응이 존재함을 보여, 크기가 같다는 결론을 얻는다. 하지만 실수 집합과 유리수 집합 간엔 일대일 대응이 존재하지 않음도 보여, 실수 집합의 크기가 유리수 집합보다 크다는 결론을 얻는다. 칸토르는 더 나아가, ‘유리수 집합보다는 크지만 실수 집합보다는 작은 무한집합이 존재하느냐󰡑질문하였고, 그런 무한집합이 없을 것이라 예상하였다. 이것이 유명한 그의 ‘연속체 가설’이다. 그는 남은 일생동안 이 문제에 매달리는데 결국 해결하지 못하고 정신병동에서 쓸쓸히 죽었다고 전해진다. 이 문제는 잘 알려진 대로 후대에 괴델과 코헨에 의해 풀리는데, 뒤에서 좀 더 언급할 것이다.

 

한편 20세기에 접어들며 수학자들은 집합론을 통해 수학의 기초를 건설하여, 모순 없고 엄밀한 수학을 재구성 할 수 있으리라는 희망에 부풀어 있었다. 하지만 이런 기대는 러셀(Bertrand Russell)의 역리라 불리는 다음과 같은 문제가 발견되며 흔들리게 된다.

 

칸토르의 집합론은 특정성질을 공통으로 갖는 원소들의 집합은 항상 존재한다고 전제한다. 그렇다면 자기 자신을 원소로 갖지 않는 원소들을 모은 집합 가 존재한다. 집합기호를 쓰면,

이다. 즉 는 성질 (원소 는 자기 자신 를 원소로 갖지 않는다)를 만족하는 원소들의 집합이다. 우선 여기서 가 의 원소라 가정해 보자. 즉 라 하자. 그러면 집합 는 자신 의 원소가 되어, 성질 를 만족해야 하므로, 가 된다. 기호로 나타내면

이다. 그렇다면 이번엔, 가 의 원소가 아니라고 가정해 보자. 즉 라 하자. 그렇다면 는 성질 를 만족하는 원소(집합은 동시에 원소이기도 하다)이므로, 에 들어간다. 즉

가 유도된다. 정리하면

라는 모순된 결과를 얻는다.

 

러셀의 역리로 인해, 수학의 기초를 세우는데 이와 같은 모순이 생기지 않는, 수정되고 좀 더 심대한 집합론 및 수학 기초론의 등장이 요구되었다. 이 후 이러한 문제를 해결하기 위한 학파들이 등장하여 각 자의 주장을 펼치게 된다. 괴델이 수리논리학을 연구하고자 결심한 1920년대의 상황이 이러했던 것이다.

 

조금만 상상력을 동원하면, 이 시점이 서구 수리과학역사에 있어서 매우 혼란스러우면서도, 동시에 새로운 도약의 계기가 되는 시점임을 간파할 수 있다. 과학의 근간이 되는 수학의 세밀한 전개가 요구되던 즈음, 그 도구로 각광받던 집합론에 근본적 결함이 발견되었다. 이는 조금 과장되게 표현하면 인류의 역사와 더불어 시작된 과학성과 전체가 송두리째 무너질 수도 있다는 위기감과 동시에, 이를 타개하기 위한 새로운 학문적 인식이 태동해야 한다는 절박감이 감돌던 시기라 볼 수 있다.

 

당시 급진적인 견해를 피력하는 부류도 있었고, 수학을 논리학에 귀속시키려는 시도도 있었다. 하지만 가장 널리 받아들여지고, 오늘날 현대 수학의 근간이 되는 정론은 힐버트(Hibert)의 형식주의 또는 공리론적방법론이다. 이를 한마디로 설명하긴 매우 힘드나, 불완전하나마 요약해보자. 우선 인간의 언어가 가지는 결함을 제거하기위해 모든 수학의 명제를 형식적 기호의 나열로 바꾼다. 그런 명제들 중, 모순이 생성되는 요소를 피하여 수학의 공리들을 세우고, 거기서 새로운 명제를 유도하는 법칙을 세운다. 이해하기 쉽게 설명하면, 일종의 기계적 프로그램으로 수학을 이해하자는 것이다. 힐버트는 이러한 형식적이고 기계적 체계 하에서, 수학의 기본 공리를 세심히 설계하면, 모순이 절대로 유도되지 않는 것을 보일 수 있으리라 예상했다. 그리하여 러셀의 역리와 같은 문제가 발생하지 않는 수학의 기초가 다져지는 것을 기대한 것이다. 이것을 ‘힐버트 프로그램’이라 부른다. 실제로 체르멜로(Zermelo)는 힐버트의 생각을 구현하여, 요즘 체르멜로-프랭켈 공리라 불리는, 모순이 없을 것으로 예상되는 집합론의 공리들을 제안하였다.

 

앞으로 다시 돌아가, 괴델이 비엔나에서 공부하던 시절에 대해 얘기를 계속해

보자. 지도교수 한의 초대로 비엔나 서클에 합류하여, 오랜 동안 정기적으로 회합에 참석했다고 한다. 이러한 교류가 그의 학문적 성장에 기여했음은 자명하다. 1930년 그는 힐버트가 제시한 수리논리체계의 완비성에 관한 논문으로 박사학위를 받는다. 이에 대한 소개는 생략하겠다. 다만 수리논리학 전문가들에게, 그의 유명한 불완전성 정리(앞으로 상세히 설명할 것이다)보다도, 이 완비성 정리가 더 유용하게 현재까지도 쓰인다는 것을 지적하고 싶다. 불완전성 정리는 ‘...를 할 수 없다’는 부정적 결과이나, 완비성 정리는 역으로 긍정적 결과이기에 그렇지 않나 싶다.

 

이듬해인 1931년, 드디어 20대의 나이에 학계를 깜짝 놀라게 한, 세기적 결과인 불완전성 정리를 발표한다. 그의 불완전성 정리를 한마디로 말한다면, ‘참인 것이 분명하나, 증명할 수 없는 수학적 명제가 존재 한다’는 것이다. 도대체 이것이 무슨 말인가? 증명되지 않는 명제가 참인 것을 어떻게 알 수 있다는 말인가? 그렇다면 증명된다는 것과 참이라는 의미의 차이는 무엇인가? 필자를 비롯한 많은 수리논리학 연구자들은, 그들이 수리논리학을 전공한 계기가 이것이라 고백한다. 즉 학생시절 불완전성 정리의 오묘함을 접하고 깊은 인상을 받은 가운데 그것을 온전히 이해하고자 하는 시도가 연구자의 길로 이어졌다는 것이다.

 

그의 정리는 세밀히는 제일, 제이 불완전성 정리들로 나눠진다. 제일 불완전성 정리는 대략적으

 

로 서술해서, 수학에서는 증명도 부정도 되지 않는 명제가 반드시 존재한다는 것이다. 사실 이것은 앞서 언급한 칸토르의 연속체 가설과 연관된다. 괴델은 연속체 가설이, 제Ⅰ불완전성 정리에서 나타나는 것처럼 증명도 부정도 안 되는 명제일 것이라 추측하였다. 마침내 그는 1930년대 중반, 연속체 가설이 수학에서 ‘부정되지 않는 명제’임을 증명하는데 성공한다. 그 후 1960년대에 와 비로서 코헨(Cohen)이란 젊은 수학자에 의해 연속체 가설이 ‘증명도 되지 않는 명제’임이 밝혀짐으로 연속체 가설 문제의 종지부가 찍힌다. 코헨은 그 업적으로 수학자 최고상이라 할 수 있는 필드상을 받는다.

 

제Ⅱ 불완전성 정리는 더욱 놀랍다. 수학을 전개하는 근본 공리를 선정하여 그 체계가 정말 모순이 없다면, 그 모순이 없다는 사실자체는 (그 체계의 논리전개로는) 증명을 할 수 없다는 것이다. 이것은 앞서 언급한 힐버트의 프로그램이 성취될 수 없다는 것을 의미한다. 수리학문계는 다시 한 번 커다란 충격과 놀라움에 휩싸인다. 최근 황우석 박사 사건으로 나라 전체가 엎치락뒤치락 했던 것 이상의 상황이라 할 수 있겠다. 괴델의 정리는 힐버트나 그 이전 수학자들이, ‘우리가 알고자 하는 수학적 문제들은 결국에 진리이거나 거짓으로 판명 또는 증명될 것이라’는 당연하다고 여긴 믿음이 옳지 않다는 것이다. 이는 인간 인식에 근본적 한계가 있음을 극명하게 보여준 하나의 세기적 사건이었다.

 

불완전성 정리로 힐버트의 원래 의도 했던 계획이 무산됐다고 해서 그의 형식주의가 사라진 것은 아니다. 그가 처음 제시했던 수학의 형식적 재구성에 관한 철학과 관점은 계속 유효하고 올바른 방향이라 여겨졌고, 현대수학은 그의 형식주의의 발전에 바탕을 두고 있다. 즉, 인간의 근본적 인식의 한계로 인해 힐버트가 원하던 것을 100% 얻을 순 없다 하더라도, 그의 주장은 기본적으로 옳았다는 것이다. 따라서 불완전성 정리는 칸토르 이 후 제기돼왔던 수학 기초론의 기본 논의를 무너뜨린 것이 아니라, 오히려 문제의 본질을 드러내고, 한계 가운데 계속적 작업을 해야 함을 알려 준 것이다. 따라서 이 후, 대부분의 수학자들이 수학기초론의 근본적 인식에 동의하게 되는 계기를 마련하여, 출렁이던 초기 수리논리학 역사가 안정되고 급속한 후속 진보를 이루는 토대가 된 것이다.

 

뿐만 아니라 괴델의 불완전성 정리는 분석철학, 인식론에 영향을 미치고, 언어학, 현대의 인지과학에 까지 파급을 끼친다. 논리학 내에서는 정리의 확장이, 양상논리라는 형태로 발전하여 오늘에 이른다. 정리의 증명에 사용된 코딩이론, 계산가능성 정의 등은, 후 대 튜링(타임지가 선정했던 두 번째 수학자), 본 노이만(von Neumann) 등에 의해 발전되어 최초 현대적 컴퓨터 설계의 이론 배경이 된다.

 

불완전성 정리와 증명에 대한 본격적 설명을 잠시 뒤로 미루고 계속, 괴델의 이후 업적과 삶을 추적해 보자. 불완전성 정리 이후 연속체 가설에 관한 중요한 결과를 얻은 것을 앞에서 설명했다. 이때가, 육체적 정신적 건강문제로 시달시던 시기였음에도, 당 시 미국 프린스턴에 갓 설립된 고등과학연구소(Institute for Advanced Study)에 주기적으로 방문한다. 1930년대 후반 당시 베엔나의 정치적 상황은 혼란스러웠다. 나치에 의해 주도된 반유대주의 물결로 지도교수였던 한이 유대인이란 이유만으로, 괴델 자신도 불이익을 당할 입장이었다. 한편 당시 학문적으로 유럽에 비해 한 수 아래였던 미국은, 고등과학연구소 설립을 기반으로 괴델, 아인슈타인 등 당대 최고의 수학자, 물리학자들을 영입하려 계획하였고, 괴델 자신도 마침내 미국으로 영구 이주하길 결심한다. 징집과 비자 등의 문제가 있었으나, 드디어 1940년 초, 1938년 결혼한 아내와의 고등과학원으로의 이주가 실현되었다.

 

1978년 사망할 때 까지 괴델은 프린스턴에 머물고 미국 시민권을 취득한다. 자식은 없었다고 전한다. 당시 고등과학원의 아이콘들이라 할 수 있던 괴델과 아인슈타인은 깊은 친분관계를 유지하였다. 괴델은 우주론의 시간여행과 관련한 주요업적을 1949년경 이루는데, 이는 다분히 아인슈타인의 영향이 컷을 것이라 알려진다. 아인슈타인이 상대적으로 활발한 사회활동을 하고 당시 대중의 인기를 누렸던 것에 비해, 괴델은 조용한 은자 같은 모습을 보였다. 이것이 아인슈타인에 비해 괴델이 일반인에게 상대적으로 덜 알려진 이유 중 하나일 것이다.

 

그는 사실 우울증 등 정신 질환으로 시달렸는데, 연속체 가설에 관한 결과를 얻을 당시 이로 인해 요양소에 입원하기도하고, 뒤따른 무력증으로 결과의 출판이 지연되기도 하였다. 자신의 건강에 문제가 있을 거란 의심은 어린 시절 이 후 계속되었고, 실제로 1951년에는 궤양출혈로 생사를 헤매기도 하였다. 그는 편집증으로, 미국을 벗어나면 되돌아 올 수 없을지도 모른다고 생각하였고, 1940년 이주 후 한 번도 국외 여행을 하지 않는다. 말년, 편집증세의 심화로 음식섭취를 거부하였고, 결국 죽음에 이른다. 학문세계의 지형도를 변화시킨 천재임에도 그의 퇴장은 이렇게 쓸쓸하였다.

 

이제부턴, 약속한데로 그의 불완전성 정리에 대해 좀 더 구체적으로 알아보자. 먼저, 제Ⅰ, 제Ⅱ 불완전성 정리를 더 전문적이게 서술할 것이다. 이 후 누구나 접근이 용이한 방법으로 그의 아이디어와 증명방법을 간략하게 요약하겠다. 여기까지에 만족 못 할 분들을 위해 부록에서, 좀 더 형식적인 방법으로 그의 정리를 집합론적 관점에서 기술할 것이다.

 

제Ⅰ불완전성 정리는 다음과 같다. 임의의 수리논리체계가 첫째, 모순이 없고, 둘째, 그 체계의 공리를 판별할 수 있는 구현 가능한 방법(예를 들어 컴퓨터 프로그램)이 존재하며 셋째, 산술의 기초(덧셈과 곱셈의 기본 관계)를 도출할 수 있으면, 그 체계는 불완전하다. 즉, 그 체계로부터 증명도 반증도 안 되는 명제가 반드시 존재한다.

제Ⅱ불완전성 정리에서도, 전제들은 제Ⅰ정리의 경우와 같다. 즉, 임의의 수리논리체계가 첫째, 무모순하고, 둘째, 그 체계의 공리를 판별할 수 있는 실현가능한 방법이 존재하며 셋째, 산술의 기초를 도출할 수 있으면, 그 체계로부터 자신의 체계가 모순이 없다는 것을 증명할 수 없다. 좀 더 정확히는 ‘자신의 체계가 무모순하다는 것’을 의미하는 명제가 증명되지 않는다.

 

제Ⅰ, 제Ⅱ정리에 공통으로 들어가는 세 가지 전제는 매우 중요한 의미를 갖는다. 이 세 전제들은 서로 독립이어서 그들 중 하나라도 만족하지 못하면 제Ⅰ, 제Ⅱ정리는 유도되지 않는다. 특히 두 번째 전제인 ‘구현 가능한 방법’의 구체적 의미와 그 변용은 현대 전산이론의 토대 역할을 한다. 이 의미는 다르게 설명하면, 혹 공리들이 무한히 많다 하더라도, 그 공리를 판별할 수 있는 유한하게 기술된 알고리듬(또는 컴퓨터 프로그램)이 있는 경우를 말한다. 즉 알고리듬에 들어가는 입력 데이터를, 대상이 되는 논리체계의 (코드화된) 명제라 하자. 그 알고리듬은 유한 시간 내에, 유한 과정을 거쳐, 입력된 명제가 공리들 중의 하나인지 아닌지를 판별해 내야 한다.

 

이 전제들을 만족하는 체계로, 산술을 공리화한 페아노(Peano)체계, 집합론의 공리체계인 체르멜로-프랭켈 체계들이 있다. 두 경우 모두 공리들이 무한이 많으나, 어떤 것이 그 공리이지 아닌지를 판별할 수 있는 인식 가능한 방법을 제시할 수 있기에 두 번째 전제를 만족한다. 또한 두 체계 모두 당연히 더하기와 곱하기를 설명할 수 있기에 셋째 전제도 만족하는 것이다. 따라서 체르멜로-프랭켈 공리체계의 경우로 불완전성 정리를 다시 기술하면, 그 공리체계는 집합론의 공리체계이기에 우리가 하는 ‘수학’이라고 큰 관점에서 말할 수 있고, 그러므로 우리의 수학에 (첫째 전제) 모순이 없다면, 수학은 (제Ⅰ정리에 의해) 불완전하여 증명도 반증도 되지 않는 명제가 반드시 있고, (제Ⅱ에 의해) 수학 자신의 무모순성은 증명할 수 없다는 것이다.

 

제Ⅰ, 제Ⅱ정리를 통괄하여 ‘진리이나 증명되지 않는 수학적 명제가 존재 한다’로 요약할 수 있다. 제Ⅱ정리의 경우, 방금 살핀 것과 같이, ‘수학이 무모순하다’는 명제 자체는 진리여야 함에도, 증명될 수 없다는 것이다. 제Ⅰ정리의 경우도, 수학에서 증명도 반증도 되지 않는 명제는, 플라톤적 관점에서 그 자신 또는 자신의 부정명제 둘 중 하나는 참일 수밖에 없으나, 어느 것도 증명되지 않는다.

 

이제 다음으로, 불완전성 정리의 증명을, 최대한 이해할 수 있게 설명하려 한다. 괴델의 불완전성 정리가 ‘진리이나 증명되지 않는 수학적 명제가 존재 한다’로 요약된다고 앞에서 설명하였다. 괴델이 그러한 명제를 어떻게 찾았는가를 설명할 것이다. 괴델의 획기적 아이디어 중 하나는, 각각의 수학적 명제를 수(0보다 큰 양의 정수)로 바꾸어 생각할 수 있다고 본 것이다. (이는 요즘의 사람들에게 낯선 생각이 아니다. 디지털 컴퓨터의 세계에서는, 입력 데이터가 무엇이던 그것이 0과 1의 조합으로 나타나는 것을 생각하면 된다.) 즉 임의의 ‘수학적 명제’에 수자 코드(그 명제의 ‘괴델 수’라 부른다)를 주는 방법을 제안한 것이다. 예를 들어,

 

‘17은 소수이다’라는 명제의 괴델 수를 10098762,

 

페르마의 정리 ‘수 이 2보다 크면, 을 만족하는 수 가 존재하지 않는다’의 괴델 수를 4328937739479304,

 

명제 ‘ ’의 괴델 수를 209872987,

 

현재까지도 미해결인 골드바하(Goldbach)의 예상 ‘4 이상의 짝수는 두 개의 소수의 합으로 표시 된다’의 괴델 수를 85640032815라 하자.

 

위의 네 명제 중, 첫째 명제는 진리이고, 둘째 명제도 350년간 미해결 상태로 있다가, 최근 프린스턴대 교수 와일스(Wiles)에 의해 진리임이 확인되었다. 셋째 명제는 거짓이고, 넷째 명제는 진리인지, 거짓인지 아직 모른다.

 

여기서 ‘증명 수’에 대해 정의해 보자. 어떤 수가 증명 수라함은 그 수가 우선 한 명제의 괴델 수이고, 그 명제는 수학에서 증명될 수 있을 경우를 뜻한다. 즉, 위의 괴델 수들 경우 방금 설명한 것처럼, 10098762, 4328937739479304는 모두 증명 수이고, 209872987은 증명 수가 아니며, 끝으로 85640032815는 증명 수인지 아닌지 아직 모른다.

 

괴델 정리 증명의 핵심은, 괴델이 다음을 만족하는 수 이 존재하는 것을 보인 것이다.

 

(1) 수 은 ‘ 은 증명 수가 아니다’라는 명제의 괴델 수이다.

 

그 수 을 예를 들어 56200981239472018009이라 해 보자. 여기서,

 

(2) ‘56200981239472018009는 증명 수가 아니다’

 

라는 명제는 증명될 수 없다. 왜냐하면 명제 (2)가 증명된다면, 증명 수의 정의에 의해, 명제 (2)의 괴델 수는 증명 수가 된다. 그렇다면 (1)에서, 명제 (2)의 괴델 수가 56200981239472018009라고 했으므로, 56200981239472018009는 증명 수이다. 이는 명제 자신의 선언과 위배된다. 따라서 명제 (2)는 증명될 수 없다.

 

위 논의는 하지만, 명제 (2)는 사실임을 얘기한다. 명제 (2)가 증명되지 않기에, 그 명제의 괴델 수 56200981239472018009 자신은 증명 수가 될 수 없는 것이다. 이상을 정리하면 명제 (2)는 ‘진리임에도 증명되지 않는’, 우리가 찾고자 하던 명제인 것이다.

 

이상의 설명으로 인해 불완전성 정리에 대한 이해가 한편으론 더해진 것 같기도 하면서, 동시에 그것에 대한 의문도 깊어진 것을 부인할 수 없을 것이다. 완벽하게 불완전성 정리를 이해하고 싶은 마음이 더 생겨났다면 필자의 의도가 성공한 것이리라. 이를 위해선 사실 한 학기 강의 수강이 필수적이다. 필자는 MIT와 연세대에서 관련 강의를 해왔는데, 수학과 학생은 기본이고 철학과, 물리학과, 공대 학생들도 다수 수강하였다. 특히 MIT에서는 전산과 학생들을 포함, 천문학, 언어, 정치를 전공하는 학생들도 관심을 가지고 수강하였고, 종종 이들 인문학 전공자가 최고 성적을 내기도 하였다. 강의 첫 시간 학생들에게, 이 한 학기 강의를 재미있는 스토리가 전개되는 영화를 보는 것처럼 생각하라고 얘기한다. 초기에, 증명에 요구되는 기본 개념들을 하나하나 배우고, 끝에 가서 이것들이 종합되고 어우러지며 아름다운 증명이 전개된다. 마치 영화에서 각자의 배경을 가진 주인공들의 이야기가, 클라이맥스를 통해 조화되고 연결되며, 결말을 보이는 것과 비슷하다하겠다. 최근 한 대학생이, 미국 거대 전산회사의 우주여행 홍보사업에 당선되어, 조만간 한국인으로 최초의 우주여행을 한다고 한다. 우주 체류시간은 한 시간이고, 자기 돈으로 여행을 할 경우 1억이 넘는 비용이 필요하단다. 실제로 몇몇 갑부들은 이 경비를 지불하고 여행을 했다고 한다. 인간으로 태어나 인류최대 난제중 하나를 이해하는 것은, 우주여행을 경험하는 것 이상의 감동을 선사할 것이다. 비용은 들지 않으면서도, 한 시간이 아닌, 한 학기의 동안의 감상과 그 이후의 감동이 평생을 가리라 자부한다.

 

괴델의 탄생 100주년을 맞는 올 해 2006년, 이 글을 통해, 인류의 인식의 발전에서 최고라 할 수 있는 괴델의 정리를 이해하고자 하는 사람들이 더 많아지길 기대한다. (이 글을 쓰면서 괴델의 일생에 관해 참고한 책은, 펜실배니아 주립 대 교수인 존 도슨(John Dawson)의 영문판 책 Logical Dilemmas, The Life and Work of Kurt Gödel (A K Peters, 1997)이다.)

 

부록

여기서 형식적인 방법으로, 집합론체계 내에서 괴델 정리를 기술하려한다. 먼저 집합론의 진술들을 ‘정식(formula)’이라 부르는데, 다음과 같이 구성된다. 쓰이는 기호들은 연결기호 , , , , , 양화(量化)기호(quantifier) , , 보조기호 (, ) 그리고 술어(述語)기호 , , 끝으로 변항기호 , , ,...들이다. 이들이 다음과 같이 연결될 때 ‘정식’이라 부른다. 우선 , 또는 는 정식이다. 와 가 정식이면 , , , , 모두 정식이고, 와 도 정식이다. 예를 들어 는 정식이다. 이 정식에서 는 양화기호 에 한정돼 있는데, 이 경우 ‘변항 가 한정돼있다’고 한다. , 는 한정돼있지 않으므로 자유변항이라 한다. 정식을 보통 으로 표시하는데, 이는 변항 이 정식 의 자유변항이라는 의미다. 정식에 자유변항이 하나도 없는 경우를 명제, 또는 문장(sentence)이라 부른다.

예를 들어 위의 정식에 를 붙인 는 명제가 된다.

 

다음 작업은, 논리적 공리들을 나열하는 일이다. 여기서 구체적으로 열거하진 않겠으나, 일반적으로 자명하여 공리로 채택하고 싶은 명제들을 포함