괴델의 불완전성 정리, 낙원의 한계

ZFC 공리계라는 견고한 토대 위에 집합론이 새로운 시대를 맞이하고 있을 무렵, 수학의 세계에는 또 한 명의 젊은 천재가 혜성처럼 등장하여 그 기초를 다시 한번 뒤흔들 준비를 하고 있었다. 그의 이름은 쿠르트 괴델(Kurt Gödel). 오스트리아 출신의 이 젊은 논리학자는 20세기 수학과 철학에 가장 심오한 영향을 미친 인물 중 한 명으로 평가받는다.

괴델의 관심사는 수학의 기초, 특히 형식적인 공리 체계의 능력과 한계에 대한 것이었다. 당시 다비트 힐베르트는 수학의 모든 문제가 유한한 절차를 통해 해결될 수 있으며, 수학 체계 전체의 무모순성을 증명할 수 있다는 ‘힐베르트 프로그램’을 야심 차게 추진하고 있었다. 많은 수학자들이 이 프로그램의 성공을 믿어 의심치 않았고, 수학은 마침내 완벽하고 모순 없는 절대적인 진리의 체계로 완성될 것처럼 보였다.

그러나 1931년, 스물다섯 살의 젊은 괴델은 「수학 원리 및 관련 체계들의 형식적으로 결정 불가능한 명제에 관하여(Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I)」라는 제목의 논문을 발표하며 이러한 낙관론에 찬물을 끼얹었다. 이 논문에 담긴 내용이 바로 그 유명한 ‘괴델의 불완전성 정리(Gödel's incompleteness theorems)’였다.

불완전성 정리는 크게 두 가지 중요한 내용을 담고 있다.

제1 불완전성 정리: 산술을 포함하는 충분히 강력하고 모순이 없는 형식적인 공리 체계에는, 그 체계 내에서는 참이지만 증명할 수도 없고 반증할 수도 없는 명제가 반드시 존재한다.

이것은 실로 충격적인 결과였다. 힐베르트가 꿈꿨던 것처럼 수학의 모든 참인 명제를 증명할 수 있는 완벽한 공리 체계는 원리적으로 불가능하다는 것을 의미했기 때문이다. 아무리 많은 공리를 추가하여 체계를 확장하더라도, 항상 그 체계의 울타리 밖으로 벗어나는 ‘결정 불가능한’ 명제가 존재한다는 것이다. 마치 인간의 이성이 스스로 그 한계를 규정하는 것과 같은 심오한 철학적 함의를 담고 있었다.

제2 불완전성 정리: 산술을 포함하는 충분히 강력하고 모순이 없는 형식적인 공리 체계는, 그 자신의 무모순성을 스스로 증명할 수 없다.

이것은 힐베르트 프로그램의 핵심 목표였던 ‘수학 체계의 무모순성 증명’이 그 체계 내부의 방법만으로는 달성될 수 없음을 보여주는 치명적인 결과였다. 수학자들은 자신들이 사용하는 공리 체계가 모순이 없다고 믿고 싶어 했지만, 그 믿음을 수학적으로 완벽하게 증명하는 것은 불가능하다는 것을 받아들여야 했다.

괴델의 불완전성 정리는 수학의 절대적인 확실성에 대한 믿음을 근본적으로 뒤흔들었다. 수학은 더 이상 모든 질문에 답을 줄 수 있는 전지전능한 학문이 아니었다. 그 안에는 영원히 미해결로 남을 수 있는 문제들과 증명 불가능한 진리들이 존재한다는 사실이 드러난 것이다.

이러한 괴델의 발견은 칸토르가 평생을 바쳐 씨름했던 ‘연속체 가설’의 운명에도 중요한 그림자를 드리웠다. 연속체 가설이란 ℵ₀와 c 사이에 다른 무한 기수가 존재하지 않는다는, 즉 c = ℵ₁이라는 주장이었다. 칸토르는 이것이 참이라고 굳게 믿었지만, 그 증명에는 실패했다.

괴델은 1930년대 후반, 이 연속체 가설 문제에 천착했다. 그는 ZFC 공리계(선택공리를 포함한 체르멜로-프렝켈 공리계) 내에서 작업하면서 놀라운 결과를 얻어냈다. 1938년, 그는 만약 ZFC 공리계가 무모순이라면, ZFC에 연속체 가설(CH)을 추가한 공리계 역시 무모순이다라는 것을 증명했다!

이것은 ZFC 공리계 내에서는 연속체 가설을 ‘반증’할 수 없다는 것을 의미했다. 만약 연속체 가설이 ZFC와 모순된다면, ZFC에 CH를 추가했을 때 모순이 발생해야 하기 때문이다. 따라서, 칸토르가 믿었던 것처럼 연속체 가설이 참일 가능성은 여전히 남아 있었다.

괴델의 이 결과는 수학자들에게 큰 희망을 안겨주었다. 어쩌면 연속체 가설은 정말로 ZFC 내에서 증명 가능한 참인 명제일지도 모른다는 기대감이 다시 고개를 들었다. 칸토르의 낙원에는 여전히 풀리지 않은 수수께끼가 남아 있었지만, 그 수수께끼가 낙원 자체를 파괴하지는 않을 것이라는 안도감이 퍼졌다.

그러나 괴델의 작업은 이야기의 절반에 불과했다. 그는 연속체 가설이 ZFC와 모순되지 않음을 보였지만, 그것이 ZFC로부터 ‘증명’될 수 있는지는 여전히 미해결 문제로 남았다. 만약 연속체 가설이 ZFC 내에서 증명될 수 없다면, 그것은 불완전성 정리가 예견한 것처럼 ZFC 체계 내에서 ‘결정 불가능한’ 명제가 될 터였다.

칸토르가 열었던 무한의 낙원. 그곳은 풍요롭고 아름다웠지만, 괴델은 그 낙원에도 인간 이성의 한계가 존재함을 명확히 보여주었다. 모든 것을 알 수 있고 모든 것을 증명할 수 있다는 순진한 믿음은 깨졌지만, 그 대신 수학은 더욱 겸손하고 심오한 학문으로 거듭나고 있었다.

이제 수학자들의 시선은 한 가지 중요한 질문으로 모아졌다. 과연 연속체 가설은 ZFC 공리계로부터 증명될 수 있을까, 아니면 증명될 수 없을까? 이 질문에 대한 답은 또 다른 천재 수학자의 등장을 기다려야 했다. 그리고 그 답은 칸토르의 예상을 다시 한번 뛰어넘는, 놀라운 것이 될 터였다. 낙원의 한계는 드러났지만, 그 안에서의 탐험은 여전히 계속되고 있었다.