수학기초론 2강. 괴델의 불완전성 정리
"이 문장은 증명할 수 없다"를 산술의 언어로 쓸 수 있게 된 순간, 수학의 완전한 요새를 짓겠다는 힐베르트의 꿈은 끝났습니다.
풀고 시작
힐베르트 프로그램: 확실성의 요새
1강의 위기에 대한 힐베르트의 처방은 정면 돌파였습니다. 1920년대에 구체화된 힐베르트 프로그램은 세 기둥으로 요약됩니다. 첫째, 수학 전체를 명시적 공리와 추론 규칙을 가진 형식 체계로 만듭니다. 둘째, 그 체계가 완전함을, 즉 모든 참인 명제가 체계 안에서 증명됨을 보입니다. 셋째, 그 체계의 무모순성을 의심의 여지가 없는 유한적(finitary) 방법만으로 증명합니다. 성공하면 무한을 다루는 칸토어의 낙원을 역설의 공포 없이 지킬 수 있죠. 힐베르트는 1930년 쾨니히스베르크 연설을 "우리는 알아야 한다, 우리는 알게 될 것이다"라는 문장으로 맺었고, 이 문장은 훗날 그의 묘비에 새겨졌습니다. 그런데 역사는 잔인한 우연을 준비해 두었습니다. 바로 그 전날, 같은 도시의 학술 토론회에서 25세의 괴델(Kurt Gödel, 1906~1978)이 조용히 결과 하나를 발표한 것입니다. 그 자리에서 의미를 즉시 알아챈 사람은 폰 노이만 정도였습니다.
두 정리의 정확한 진술
1931년 논문에서 괴델은 다음을 증명했습니다.
제1 불완전성 정리: 산술을 표현할 수 있을 만큼 강하고, 공리들을 기계적으로 나열할 수 있으며(재귀적 공리화), 무모순인 형식 체계에는, 그 체계의 언어로 쓰였지만 체계 안에서 증명도 반증도 되지 않는 문장이 존재합니다. 원 논문은 무모순성보다 조금 강한 ω-무모순성을 가정했고, 1936년 로서(J. B. Rosser)가 이를 무모순성으로 약화시켰습니다.
제2 불완전성 정리: 위 조건을 갖춘 체계는 자기 자신의 무모순성을 표현하는 문장을 스스로 증명할 수 없습니다. 이것이 힐베르트 프로그램의 셋째 기둥을 직접 겨냥합니다. 유한적 방법이 그 체계 안에 담긴다면, 체계는 자기 무모순성 증명을 산출할 수 없기 때문이죠.
여기서 과장을 경계해야 합니다. 이 정리는 "수학이 불확실하다"는 뜻이 아닙니다. 조건을 만족하지 않는 완전한 체계도 있습니다. 괴델 자신이 1929년에 1차 술어논리의 완전성을 증명했고, 덧셈만 다루는 프레스버거 산술은 완전하며 결정 가능합니다. 정리가 말하는 것은 진리 전체를 하나의 형식 체계로 남김없이 포획하려는 특정 기획의 한계이지, 수학적 지식의 붕괴가 아닙니다.
자기지시의 기술
그렇다면 괴델은 어떻게 이런 문장을 만들었을까요. 증명의 핵심 아이디어는 자기지시를 산술 안에 밀수하는 것입니다. 괴델은 모든 기호, 문장, 증명에 고유한 자연수(괴델 수)를 부여했습니다. 그러면 "문장 A는 증명 가능하다" 같은 메타 수준의 진술이 자연수들 사이의 관계, 즉 산술 문장이 됩니다. 대각화 기법으로 괴델은 "이 문장은 이 체계에서 증명 불가능하다"라고 자신에 대해 말하는 문장 G를 구성했습니다. 이제 따져 봅시다. G가 증명된다면 체계는 거짓을 증명한 셈이 되어 무모순성이 깨집니다. 따라서 체계가 무모순이라면 G는 증명되지 않고, 그렇다면 G가 말하는 내용은 표준 자연수 모형에서 참입니다. 참이지만 그 체계 안에서는 증명할 수 없는 문장이 손에 잡힌 것이죠. "이 문장은 거짓이다"라는 거짓말쟁이 역설과 달리, G는 진리가 아니라 증명 가능성을 말하므로 모순이 아니라 정리를 낳습니다. 역설의 구조를 무기로 바꾼 것, 그것이 괴델의 천재성입니다.
튜링과 계산 이론으로
힐베르트 프로그램에는 넷째 질문도 있었습니다. 임의의 수학 명제의 증명 가능 여부를 기계적으로 판정하는 절차가 있는가라는 결정 문제(Entscheidungsproblem)입니다. 1936년 튜링(Alan Turing)은 계산이라는 개념 자체를 튜링 기계로 정의한 뒤, 프로그램의 정지 여부를 판정하는 일반 절차가 없음을 보였고, 이로부터 결정 문제의 답도 부정임을 증명했습니다. 처치(Alonzo Church)도 같은 해 독립적으로 같은 결론에 도달했죠. 수학의 토대를 묻던 질문이 계산 가능성의 이론을 낳았고, 그 이론이 컴퓨터의 개념적 청사진이 되었습니다. 불완전성과 계산 불가능성은 같은 뿌리, 즉 자기지시와 대각화에서 나온 두 열매입니다.
인출 문제
이전: 1강 수학이란 무엇인가 · 다음: 3강 수학의 불합리한 유효성