괴델의 불완전성 정리

늘날 컴퓨터는 우리의 생활 전반에 영향력을 행사하고 있다. 이제 컴퓨터가 없는 현대사회란 도저히 생각할 수 없는 것이다. 인터넷의 등장, 컴퓨터의 제어 관리기능 등 현대 컴퓨터의 사용범위는 무궁무진 하다. 하지만 컴퓨터가 가진 본래의 역할은 그 이름에 고스란히 남아있다. 그것은 바로 ‘계산’ 기능이다. 도대체 이 현대 계산이론은 누가 처음으로 도입했을까? 단지 한 두 사람이 이뤄낸 성과는 아니겠지만, 학자들은 대체로 영국의 수리논리학자 앨런 튜링(Alan Turing, 1912~1954)에게 그 공을 돌린다. 그러나 조금 더 나아가 보면, 튜링은 미국의 수학자 쿠르트 괴델(Kurt Gödel, 1906~1978)의 업적과 생각을 실제 컴퓨터 설계에 확장 구현한 것이라는 학문적 사실을 확인하게 된다. 괴델과 튜링은 타임지가 선정한 지난 20세기 가장 영향력 있던 인물 100명에 든 단 2명의 수학자들이다. 두 사람은 모두 수학의 분야 중 수리논리학(수학과 논리학의 하위분야. 전산학 및 철학논리와 밀접하게 연관)에서 업적을 이뤘다는 공통점을 갖고 있다. 하지만 튜링이 괴델의 생각을 발전시켜 현대 컴퓨터 이론의 기초를 세웠다는 면에서, 우리는 괴델에 더 주목하게 되는 것이다. 가능성이 잠재돼 있던 괴델의 학창시절

쿠르트 괴델. <출처: wikipedia.org>

괴델의 업적이나 학문적 영향은 아인슈타인의 상대성 이론에 비교되곤 한다. 사실 두 사람은 그들이 머물렀던 미국 고등과학연구소를 대표하는 아이콘들이었다. 1930년대 후반의 혼란스런 정치상황에서 괴델은 오스트리아를 떠나 고등과학연구소로 영구 이주한다. 하지만 괴델은 아인슈타인에 비해 대중들에게 덜 알려져 있다. 컴퓨터가 현대사회에 미치는 영향, 인지과학의 태동 등을 볼 때 괴델의 업적이 오늘날 더욱 그 진가를 나타내고 있음에도 불구하고 이렇듯 잘 알려지지 않은 까닭은, 언뜻 그의 은둔자적 삶과도 연관이 있어 보인다. 1906년 4월 오스트리아 브르노(현 체코령)에서 태어난 괴델은 직물업계에 성공한 아버지 덕에 어린 시절을 넉넉하게 보낸 편이었다. 뭐든 질문을 잘해서 ‘왜요’ 도령(der Herr Warum: Mr. Why)으로 불린 그는 모든 과목에서 최고성적을 내는 우수하고 영민한 학생이었다. 다만 어릴 때부터 건강이 좋지 않았는데, 그는 일생 동안 스스로 읽은 의학지식을 더 신뢰하며 지나친 건강 염려증을 갖고 살았다. 이는 말년에 음식섭취를 거부해 그를 죽음에 이르게 한 원인이 되기도 했다. 1924년 오스트리아의 비엔나 대학에 입학해, 그 곳에서 십여 년간 학자로 성장하며 그의 생애 최대 업적들을 이루게 된다. 대학에서는 물리학을 시작으로 철학, 수학을 공부했는데, 지도교수 한(Hans Hahn)을 만난 이후, 그의 관심은 수리논리학에 집중된다.

한과 철학자 카르납 등이 주도한 비엔나 서클은 논리실증주의(과학의 논리적 분석 방법을 철학에 적용하고자 하는 사상)로 유명했는데, 괴델을 정식으로 초청했다. 괴델은 서클의 주된 의견들에 동의하진 않았다. 하지만 이 서클이 학생이었던 그가 학문대상을 설정하는 데 지적 자극제 및 안내서가 된 것은 분명하다. 수리논리학의 탄생과 발달 여기서 당시 수리논리학의 탄생과 발달을 잠시 살펴보자. 수리논리학은 수학의 기초를 건설하는 집합론, 기호논리학 등을 포괄하는 학문이란 의미에서 수학기초론으로도 불린다. 18, 19세기에 거듭된 수학의 성과는 엄밀성이 미처 확보되지 못한 상태에서 얻어졌다. 예를 들어 수열의 수렴성, 함수 연속성과 미분 가능성 등의 엄밀한 정의가 확립되지 않은 가운데 많은 결과들이 발견됐고, 때로는 모순되거나 잘못된 결과가 여과 없이 받아들여지기도 했다. 이런 난점들을 타개하고 수학의 기초를 건설하는 도구로 집합론이 거론됐다.

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

집합론을 확립한 게오르크 칸토어. <출처 : wikipedia.org>

집합론의 문제점 발견, 새로운 학문 요구 한편 20세기에 접어들어 수학자들은 집합론을 통해 수학의 기초를 건설하며, 모순 없고 엄밀한 수학을 재구성 할 수 있으리라는 희망에 부풀어 있었다. 하지만 이런 기대는 ‘러셀(Bertrand Russell)의 역리’라 불리는 다음과 같은 문제가 발견되며 흔들리게 된다. 칸토어의 집합론은 특정성질을 공통으로 갖는 원소들의 집합은 항상 존재한다고 전제한다. 그렇다면 자기 자신을 원소로 갖지 않는 원소들을 모은 집합 S가 존재한다. 집합기호를 쓰면 아래와 같다.

‘러셀의 역리’를 발표한 버트런드 러셀. <출처 : wikipedia.org>

즉, S는 '원소 x는 자기 자신을 원소로 갖지 않는다'는 조건을 만족하는 원소들의 집합니다. 우선 여기서 S가 S의 원소라 가정해 보자. 즉 S∈S라 하자. 그러면 집합 S는 자신 S의 원소가 돼, 성질 자기 자신을 원소로 갖지 않는다는 집합 S의 조건을 만족해야 한다. 기호로 나타내면 다음과 같다. 그렇다면 이번엔, S가 S의 원소가 아니라고 가정해 보자. 그렇다면 S는 집합 S의 조건을 만족하는 원소이므로 S에 들어간다. 즉, 아래의 결과를 유도할 수 있다. 정리하면 아래와 같은 모순된 결과를 얻는다.

러셀의 역리로 인해, 수학의 기초를 세우는데 모순이 생기지 않는, 수정되고 좀 더 심대한 집합론 및 수학 기초론의 등장이 요구됐다. 이 후 이러한 문제를 해결하기 위한 학파들이 등장해 각자의 주장을 펼치게 된다. 괴델이 수리논리학을 연구하고자 결심한 1920년대의 상황이 이러했던 것이다. 조금만 상상력을 동원하면, 이 시점이 서구 수리과학역사에 있어서 매우 혼란스러우면서도, 동시에 새로운 도약의 계기가 되는 시점임을 알아차릴 수 있다. 과학의 근간이 되는 수학의 세밀한 전개가 요구되던 즈음, 그 도구로 각광받던 집합론에 근본적 결함이 발견됐다. 이는 조금 과장되게 표현하면, 인류의 역사와 더불어 시작된 과학성과 전체가 송두리째 무너질 수도 있다는 위기감과 동시에, 이를 타개하기 위한 새로운 학문적 인식이 태동해야 한다는 절박감이 감돌던 시기라 말할 수 있다.

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

집합론의 공리를 제안한 힐베르트. <출처: wikipedia.org>

학계를 깜짝 놀라게 한 ‘불완전성 정리’ 발표 1931년, 괴델은 20대의 나이에 학계를 깜짝 놀라게 한 세기적 결과인 불완전성 정리를 발표한다. 이것이 바로 괴델을 유명하게 만든 이론이다. 이 정리의 증명 속에는 앞서 컴퓨터에서 언급한 계산이론의 토대가 담겨져 있다. 괴델의 정리는 너무나도 신비하게 들려서, 일생을 들이더라도 그것에 대해 완벽하게 이해해야겠다는 갈구가 생길 정도이다. 불완전성 정리를 한마디로 요약하긴 힘드나, 축약해본다면 ‘진리임에도 증명될 수 없는 수학적 명제가 존재한다’는 것이다. 도대체 이것이 무슨 말인가? 수학적 명제는 증명을 통해 진리임이 밝혀지는데, 증명될 수 없는 명제가 진리인 것은 어떻게 알 수 있는가? 그러면 수학적 진리란 무엇이고, 그것을 증명한다는 의미는 정확히 무엇인가? 그의 정리는 제일, 제이 불완전성 정리들로 나눠진다. 제일 불완전성 정리는 대략적으로 서술하면, 수학에서는 증명도 부정도 되지 않는 명제가 반드시 존재한다는 것이다. 사실 이것은 앞서 언급한 칸토어의 연속체 가설과 연관된다. 괴델은 연속체 가설이, 제일 불완전성 정리에서 나타나는 것처럼 증명도 부정도 안 되는 명제일 것이라 추측했다. 마침내 그는 1930년대 중반, 연속체 가설이 수학에서 ‘부정되지 않는 명제’임을 증명하는데 성공한다. 그 후 1960년대에 와 비로소 코헨(Paul J. Cohen)이란 젊은 수학자에 의해 연속체 가설이 ‘증명도 되지 않는 명제’임이 밝혀짐으로 연속체 가설 문제의 종지부가 찍힌다. 코헨은 그 업적으로 수학자 최고상이라 할 수 있는 필즈(Fields)상을 받는다. 제이 불완전성 정리는 더욱 놀랍다. 수학을 전개하는 근본 공리를 선정해 그 체계가 정말 모순이 없다면, 그 모순이 없다는 사실 자체는 (그 체계의 논리전개로는) 증명을 할 수 없다는 것이다. 이것은 앞서 언급한 힐베르트의 프로그램이 성취될 수 없다는 것을 의미한다. 수리학문계는 다시 한 번 커다란 충격과 놀라움에 휩싸인다. 괴델의 정리는 힐베르트나 그 이전 수학자들이, ‘우리가 알고자 하는 수학적 문제들은 결국 진리이거나 거짓으로 판명 또는 증명될 것이라’는 당연하다고 여겼던 믿음이 옳지 않다는 것이다. 이는 인간 인식에 근본적인 한계가 있음을 매우 분명하게 보여준 하나의 세기적 사건이었다. 제일, 제이 정리를 한마디로 요약하면, ‘진리이나 증명되지 않는 수학적 명제가 존재한다’이다. 제이 정리의 경우, 방금 살핀 것과 같이, ‘수학에 모순이 없다’는 명제 자체는 진리여야 함에도, 증명될 수 없다는 것이다. 제일 정리의 경우도, 수학에서 증명도 반증도 되지 않는 명제는, 플라톤적 관점에서 그 자신 또는 자신의 부정명제 둘 중 하나는 참일 수밖에 없으나, 어느 것도 증명되지 않는다. 괴델은 참인 수학적 명제들의 범위가, 인간이 궁극적으로 증명의 방법을 통해 참으로 확인해 인식할 수 있는 명제들의 범위를 넘어선 것을 보인 것이다. 이를 위해 우선 `인간이 참으로 인식 또는 증명할 수 있는 명제'들의 범위를 규정하기 위해 `계산 가능하다'는 개념을 최초로 제안하게 된다. 나중에 튜링과 후대 학자들에 의해 정의가 확장 보강되고, 튜링은 그렇다면 기계적 프로그램으로 `계산 가능하다는 개념'을 실행하는 장치를 만들 수 있지 않을까 생각했고, 실제 컴퓨터를 설계하기에 이른 것이다. 불완전성 정리가 미친 영향 불완전성 정리로 힐베르트의 원래 의도 했던 계획이 무산됐다고 해서 그의 형식주의가 사라진 것은 아니다. 그가 처음 제시했던 수학의 형식적 재구성에 관한 철학과 관점은 계속 유효하고 올바른 방향이라 여겨졌고, 현대수학은 그의 형식주의의 발전에 바탕을 두고 있다. 즉, 인간의 근본적 인식의 한계로 인해 힐베르트가 원하던 것을 100% 얻을 순 없다 하더라도, 그의 주장은 기본적으로 옳았다는 것이다. 따라서 불완전성 정리는 칸토어 이후 제기돼 왔던 수학 기초론의 기본 논의를 무너뜨린 것이 아니라, 오히려 문제의 본질을 드러내고 한계 속에서도 계속 작업을 해야 함을 알려 준 것이다. 따라서 이후, 대부분의 수학자들이 수학기초론의 근본적 인식에 동의하게 되는 계기를 마련해, 출렁이던 초기 수리논리학 역사가 안정되고 급속한 후속 진보를 이루는 토대가 된 것이다. 뿐만 아니라 괴델의 불완전성 정리는 분석철학, 인식론에 영향을 미치고 있으며, 언어학, 현대의 인지과학에 까지 파급력을 끼치고 있다. 논리학 내에서는 정리의 확장이, 양상논리라는 형태로 발전해 오늘에 이른다. 정리의 증명에 사용된 코딩이론, 계산가능성론 등은 후대 튜링, 폰 노이만(von Neumann) 등에 의해 발전돼, 세계 최초의 현대적 컴퓨터 설계를 위한 이론 배경이 된다. 2006년에는 괴델의 탄생 백주년을 맞아 오스트리아 비엔나 대학에서 기념학술대회가 개최됐다. 여러 분야의 학자들이 참가했으며 괴델의 우주론, 이론 컴퓨터 학에 미친 괴델의 공헌에 대한 발표가 있었다. 괴델의 업적이 신학, 철학 등의 인문학과 인지과학에 미친 영향에 대한 보고가 다음날 계속 됐다. 그의 주 연구 분야였던 집합론, 수리논리학에서 현대에도 계속되는 영향과 결과들의 발전에 대한 발표가 뒤를 이었다. 지난 세기 학자들 중 이렇게 다양한 분야에 지대한 자취를 남긴 사람이 있었던가? 그와 그의 업적에 대한 향연은 끝난 것이 아니라 세월이 흐를수록 더욱 커져가고 있다.