칸토어의 집합론과 괴델의 불완전성 정리

18세기와 19세기는 수학에 있어 엄청난 발전을 이루었던 수학의 황금기였다. 17세기에 뉴턴과 라이프니츠에 의해 발견 된 미적분학과 근대해석학은 18세기에 이르러 엄청나게 발전하였고. 19세기에 이르러선 수학의 개념이 점점 추상화 되기 시작하였다. 기존의 상식으로는 설명할 수 없는 비유클리드기하(Non Euclidean geometry)가 로바체프스키(Nikolai I. Lobachevsky), 야노시(János Bolyai), 리만( Bernhard Riemann) 등에 의해 발견되었고, 아벨(Niels Henrik Abel)과 갈루아(Évariste Galois)에 의해 군론, 추상대수학이 발전하게 되었다. 이와 같이 수학이 기존과 달리 점차 복잡해지고 기존의 직관과 상식에 벗어나 점차 형식화, 추상화 되어 가면서, 스스로의 진리 여부를 검토하게 되었다. 칸토어(Georg Cantor)는 이런 난점들을 타개하고 수학의 기초를 건설하기 위하여 집합론을 제시하였다.

칸토어는 집합론의 논법으로, 당시까지 미지의 영역으로 터부시 되어왔던 무한의 개념을 엄밀하게 다루고자 하였다. 특히 주어진 두 무한 집합 사이의 크기(cardinality) 비교를 일대일 대응으로 생각하였는데, 예를 들어 자연수 집합은 유리수 집합의 부분집합이지만, 서로간의 일대일 대응이 존재하므로 두 집합의 크기가 같다는 결론을 얻을 수 있었다. 하지만 대각선 논법을 통해 실수 집합과 유리수 집합 사이에는 일대일 대응이 존재하지 않음을 보여, 실수 집합의 크기가 유리수 집합보다 크다는 결론을 얻었다. 칸토어는 더 나아가, '유리수 집합보다는 크지만 실수 집합보다는 작은 무한집합이 존재하는가' 라는 질문을 던졌고, 그런 무한집합은 없을 것이라 예상했지만 스스로 증명해 내는데에는 실패하였다. 이 문제가 유명한 '연속체 가설'(continuum hypothesis)이다.

한편, 20세기에 접어들어 수학자들은 집합론을 통해 수학의 기초를 건설하고, 이를 바탕으로 모순이 없는 엄밀한 수학체계를 재구성 할 수 있으리라는 희망에 부풀어 있었다. 하지만 이런 기대는 러셀(Bertrand Russel)에 의해 흔들리게 된다. 기존의 칸토어의 집합론은, 특성 설질을 공통으로 갖는 원소들의 집합은 항상 존재한다고 전제하였다. 이에 대하여 러셀은 근원적인 질문을 던졌는데, 러셀의 패러독스(Russell's paradox)라고도 불리는 이 질문은 다음과 같다. 자기 자신을 원소로 포함하지 않는 모든 집합들의 집합 \(Z = \lbrace A \ \vert A \notin A \rbrace \)에서 Z는 자기 자신에 속하는가, 또는 속하지 않는가? 만약 \(Z\)가 \(Z\)에 속한다고 하면, 정의에 따라 \(Z\)는 \(Z\)에 속하지 않게 된다. 하지만 만약 \(Z\)가 \(Z\)에 속하지 않는다고 하면, 또 다시 정의에 의해 \(Z\)는 \(Z\)에 속할 수 밖에 없다. 어느 경우이는 우리는 모순에 도달하게 된다. 

러셀은 이 패러독스를 알기 쉽게 설명하기 위하여 세비야의 이발사를 예로 들었는데, 이는 다음과 같다. 만약 세비야에 스스로 이발을 하지 않는 모든 이의 이발만을 해주는 이발사가 있다고 하자. 이 이발사는 스스로 이발을 해야 할까? 만약 스스로 이발을 하지 않는다면, 그 전제에 의해 자신이 자신을 이발시켜야 하고, 역으로 스스로 이발을 한다면, 자신이 자신을 이발시켜서는 안 된다. 이는 바로 러셀의 역설과 동일한 문제에 걸리는 것이다.

러셀의 패러독스는, 논리학과 집합론의 기초를 위태롭게 한다고 하여 한 때 비상한 관심을 끌었다. 과학의 근간이 되는 수학, 그리고 수학의 근간을 이루는 도구로서 각광받던 집합론에 근본적인 결함이 발견 되었다. 이러한 모순을 보완하기 위하여 공리론적 집합론(axiomatic set theory)가 등장하였다. 힐베르트(Hilbert)는 '힐베르트 프로그램'을 통하여, 모순이 생성될만한 요소를 배제한 채 수학의 공리를 세우고 이로부터 새로운 명제를 유도해 나가고자 하였다. 힐베르트는 수학의 기본이 되는 공리만 세심하게 설계할 수 있다면, 모순이 유도되지 않는 수학의 체계를 건설 할 수 있을 것이라 예상하였다. 흔히 ZFC 체계로 불리는 체르멜로-프랭켈 공리(Zermelo-Fraenkel axiom)도 그 한 예이다. 그렇다면 이제 수학의 무모순성이 보장되는 것일까? 

1931년, 괴델(Kurt Godel)은 20대의 나이에 학계를 깜작 놀라게 한 세기적 결과인 불완전성 정리(incompleteness theorem)를 발표한다. 이를 간단하게 설명하면 '진리임에도 불구하고 증명할 수 없는 수학적 명제가 존재한다'이다. 괴델의 불완전성 정리는 제 1불완전성 정리와 제 2 불완전성 정리로 나누어진다. 

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

제 2 불완전성 정리는 더욱 놀랍다. '수학을 전개하는 근본 공리를 선정해 그 체계가 정말 모순이 없다면, 그 모순이 없다는 사실 자체는 (그 체계의 공리로써) 증명을 할 수 없다'는 것이다. 이것은 앞서 언급한 힐베르트의 프로그램이 결코 성취될 수 없다는 것을 의미한다. 힐베르트는 수학적 무소순성을 보장하기위한 엄밀한 공리체계를 설계하고자 하였지만, 괴델의 제 2 불완전성 정리에 의하면, 이렇게 설계된 수학의 체계가 모순이 없다는 것을 주어진 공리체계를 통해 증명하는 것은 불가능하다. 따라서 무모순의 수학체계를 구성하는 것은 불가능하다.

괴델은 불완전성 정리를 통해, 참인 수학적 명제들의 범위가 인간이 궁극적으로 증명으로 참임을 확인할 수 있는 명제들의 범위를 넘어선다는 것을 보였다. 이를 위해 우선 '인간이 참으로 인식, 또는 증명할 수 있는 명제'들의 범위를 규정하기 위해 '계산 가능하다'는 개념을 최초로 제안하게 된다. 이 개념는 나중에 튜링과 후대 학자들에 의하여 확장 보강되고, 튜링(Alan M. Turing)에 의해 기계적 프로그램으로 `계산 가능하다는 개념'을 실행하는 장치인 컴퓨터를 설계하기에 이른 것이다.

※ 이 글은 '네이버캐스트 - 괴델의 불완전성 정리' 에 관한 글을 요약, 정리한 것입니다.