81 괴델의 불완전성 정리
— 안에서 밖을 말하는 법
81.1 힐베르트의 벽
1931년 괴델이 논문을 발표하기 전, 수학계의 꿈은 단순했다. 수학을 완전하고 무모순적인 형식 체계로 만드는 것. 이 꿈을 이끈 사람이 힐베르트였다.
문제의 발단은 이렇다. 20세기 초에 자기 자신을 가리키는 문장들이 모순을 만들어내는 사례가 발견되었고, 이것이 수학의 기초를 흔들어 놓았다. 힐베르트는 원인을 정확하게 짚었는데, 수학의 명제와 수학에 대한 명제(메타수학)를 구분하지 않아서 역설이 생긴다는 것이었다.
예를 들어 “1+1=2”는 수학의 명제이고, “’1+1=2’는 수학 명제이다”는 메타수학의 명제다. 힐베르트의 해법은 이 둘 사이에 벽을 세우는 것이었다. 수학은 숫자에 대해서만 말하고, “이 문장은 증명 불가능하다” 같은 자기언급은 메타수학이니 수학 안으로 들어올 수 없다. 벽만 잘 세우면 역설은 사라진다. 논리적으로 완벽해 보이는 방어선이었다.
81.2 괴델의 터널
괴델은 이 벽을 정면으로 부수지 않았다. 대신 아래로 터널을 팠다.
방법은 놀라울 정도로 단순하다. 모든 수학 기호에 고유번호를 매기는 것이다. 기호마다 숫자가 붙으면 모든 문장도 하나의 숫자가 되고, 모든 증명도 하나의 숫자가 된다. 이것이 괴델수라고 불리는 것인데, 쉽게 말해서 수학 문장의 바코드라고 생각하면 된다.
이 번호화가 완료되는 순간 기가 막힌 일이 벌어진다. “이 문장은 증명 가능한가?”라는 질문은 원래 메타수학의 질문이다. 문장에 대한 이야기니까. 그런데 문장에 번호가 붙어 있으면 이 질문은 “이 숫자가 어떤 산술적 성질을 갖는가?”라는 수학의 질문으로 바뀌어 버린다. 메타수학이 수학의 언어를 입고 합법적으로 들어온 셈이다.
벽이 무너진 것은 아니다. 양쪽이 같은 언어로 번역되어 버린 것이다.
81.3 자기 바코드를 자기 안에 넣다
여기서 괴델의 결정적 수법이 나오는데, 불완전성 정리에서 가장 아름다운 대목이다.
이런 문장을 하나 만든다고 해보자: “바코드 ___번 문장은 증명 불가능하다.” 빈칸이 있으니 아직 어떤 문장을 가리키는지 정해지지 않은 상태다. 완성된 문장이 아니라 숫자를 넣으면 문장이 되는 틀이다. 이 틀 자체의 바코드가 84007번이라고 하자.
이제 빈칸에 84007을 넣으면 “바코드 84007번 문장은 증명 불가능하다”가 된다. 그런데 빈칸에 숫자를 넣었으니 문장이 달라졌고, 달라진 문장의 바코드는 84007이 아니라 다른 번호가 된다. 84007을 직접 넣어서는 자기참조가 만들어지지 않는다.
괴델의 진짜 수법은 여기 있다. 빈칸에 번호를 직접 쓰지 않고, 계산 레시피를 넣는다. 이 레시피는 “틀 84007의 빈칸에 84007을 대입해서 완성된 문장의 바코드”를 계산하는 산술식이다. 이것을 \(f\)라 쓰면 괴델 문장은 이런 모양이다:
“바코드 \(f\)번 문장은 증명 불가능하다.”
\(f\)를 계산하면 무엇이 나오는가? 틀 84007의 빈칸에 84007을 대입한 결과는 바로 이 문장 자체다. 그러니까 \(f\)는 이 문장의 바코드로 귀결된다. 번호를 미리 알아서 박아 넣은 것이 아니라, 계산이 돌아가면 자기 번호에 도달하도록 설계한 것이다.
순환논리가 아니다. 번호를 붙이고 대입하는 것은 완전히 합법적인 산술 조작이다. 힐베르트가 바깥에 두려고 했던 자기언급이, 합법적 절차를 통해 체계 안에서 태어난 것이다.
81.4 참이지만 증명할 수 없다
이 문장이 참인지 거짓인지 따져보면 재미있는 결론이 나온다.
이 문장이 참이라면, 말 그대로 증명 불가능하다. 참인데 증명할 수 없는 명제가 존재하게 된다. 이 문장이 거짓이라면, 증명 가능하다는 뜻인데, 거짓인 명제를 증명할 수 있으면 체계 전체가 모순에 빠진다. 결국 체계가 모순 없이 작동하려면 이 문장은 참이면서 증명 불가능해야 한다.
이것이 제1불완전성 정리다. 여기서 한 걸음 더 나가면, 체계는 자기 자신이 모순 없다는 것조차 증명할 수 없다는 제2정리까지 따라온다. 수학은 스스로를 완성할 수 없으며, 참인데 증명할 수 없는 것이 반드시 남는다.
라마누잔의 수식이 떠오른다. 증명 없이 도착한 무한급수들은 참이었지만 아무도 증명하지 못했다. 괴델은 그런 수식이 반드시 존재할 수밖에 없음을 보였다. 라마누잔이 간극을 살았다면, 괴델은 그 간극이 구조적으로 불가피하다는 것 자체를 정리로 만든 것이다.
81.5 닫힌 문, 빈 방, 악상
갈루아는 5차방정식이라는 하나의 문을 닫았다. 근의 공식으로는 풀 수 없다는 것을 보인 것인데, 이것은 특정 문제의 불가능성이다.
괴델은 스케일이 다르다. 충분히 강한 형식 체계라면 어떤 것이든 닫히지 않는 문이 남을 수밖에 없다는 것을 보였다.
방향이 정반대인데 결론이 닮은 사례도 있다. 나가르주나는 밖에서 본질을 부정하여 안을 비웠고, 괴델은 안에서 밖을 번역하여 한계에 도달했다. 둘 다 자기완결은 불가능하다는 같은 곳에 도착한다. 나가르주나가 비운 방이 빈 방이라면, 괴델이 보여준 것은 방을 아무리 채워도 빈자리가 남는다는 것이다.
악상의 관점에서 보면, 괴델 문장은 체계가 스스로 만들어낸 악상이다. 정돈된 체계 안에서 태어났지만 그 체계로는 해결할 수 없는 진동. 오류가 아니라 데이터다.
81.6 맺음
괴델 증명이 아름다운 이유를 하나만 꼽으라면, 벽을 부수지 않고 양쪽을 같은 언어로 번역했다는 점이다. 번역이 완료되자 체계는 자기가 도달할 수 없는 곳을 정확히 가리킬 수 있게 되었다. 도달할 수 없는 곳을 가리킬 수 있다는 것, 이것이 체계가 할 수 있는 가장 정직한 행위다.
AngraMyNew가 스스로를 “장치이지 교리가 아니다”라고 말하는 것도 비슷한 구조다. 완전한 세계관이 되기를 포기하고, 자기 한계를 체계 안에서 발음한다. 괴델이 보여줬듯이, 그렇게 할 수 있는 체계만이 모순 없이 살아남는다.