수학을 완전한 공리계로 세울 수 있을까? 20세기 초 힐베르트는 모든 참인 명제를 증명할 수 있고 모순이 없는 공리계를 꿈꾸었다. 1931년 괴델은 자연수의 산술을 담을 수 있는 어떤 무모순 공리계도 참이지만 증명할 수 없는 명제를 가진다는 것을 증명했다. 수학의 한계에 대한 가장 유명한 정리이다.
핵심 개념
- 형식 체계: 기호, 공리, 추론 규칙으로 이루어진 체계. 증명은 공리에서 규칙으로 얻은 기호열이다.
- 무모순성: $P$와 $\lnot P$를 동시에 증명할 수 없다.
- 완전성: 모든 명제 $P$에 대해 $P$ 또는 $\lnot P$ 중 하나를 증명할 수 있다.
- 괴델 수: 기호와 명제, 증명을 자연수로 부호화한 것. 이를 통해 ‘증명 가능하다’는 말을 산술의 명제로 쓸 수 있다.
핵심 정리
- 괴델의 완전성 정리 (1929): 1차 논리에서 모든 모델에서 참인 명제는 증명 가능하다. (논리 자체는 완전하다.)
- 제1 불완전성 정리 (1931): 자연수의 산술을 포함하는 무모순이고 공리를 기계적으로 나열할 수 있는 체계에는, 증명도 반증도 할 수 없는 명제가 있다.
- 제2 불완전성 정리: 그런 체계는 자기 자신의 무모순성을 증명할 수 없다.
증명의 아이디어 보기
1단계: 수학을 수로. 모든 기호에 번호를 붙이고, 기호열을 소인수분해의 지수로 부호화하면(예: 기호 번호 $a,b,c$로 된 식을 $2^a3^b5^c$로), 명제와 증명이 각각 하나의 자연수가 된다. ‘$m$은 괴델 수가 $n$인 명제의 증명이다’는 자연수 $m$, $n$ 사이의 계산 가능한 관계가 되어, 체계 안에서 산술 명제 $\mathrm{Prf}(m,n)$로 쓸 수 있다.
2단계: 자기 자신을 말하는 명제. 대각선 논법(칸토어의 대각선 논법과 같은 생각)을 쓰면 다음을 만족하는 명제 $G$를 만들 수 있다.
$$G\iff\text{‘}G\text{는 증명할 수 없다’}$$
즉 ‘이 명제는 증명할 수 없다’고 말하는 명제이다.
3단계: 결론. $G$를 증명할 수 있다면 $G$가 말하는 내용이 거짓이 되므로 체계가 거짓을 증명한 셈이 되어 무모순성에 어긋난다. 따라서 $G$는 증명할 수 없고, 그렇다면 $G$가 말하는 내용은 참이다. 즉 $G$는 참이지만 증명할 수 없다. (반증도 할 수 없음을 보이려면 조금 더 강한 조건이 필요하며, 로서가 개선했다.) $\blacksquare$
‘거짓말쟁이 역설'(‘이 문장은 거짓이다’)에서 ‘거짓’ 대신 ‘증명할 수 없다’를 넣으면 역설이 아니라 정리가 된다는 것이 괴델의 통찰이다.
이어지는 결과
- 연속체 가설(‘자연수와 실수 사이의 크기를 갖는 집합은 없다’)은 ZFC에서 증명도 반증도 할 수 없다(괴델 1940, 코헨 1963).
- 튜링의 정지 문제: 임의의 프로그램이 멈추는지 판정하는 프로그램은 존재하지 않는다. 같은 대각선 논법으로 증명되며, 컴퓨터 과학의 출발점이 되었다.
확인 문제
불완전성 정리는 ‘수학에는 영원히 알 수 없는 것이 있다’는 뜻인가?
풀이 보기
정확하게는 ‘주어진 하나의 공리계로는 증명할 수 없는 참인 명제가 있다’는 뜻이다. $G$를 새 공리로 추가하면 $G$는 증명되지만, 새 체계에는 또 다른 $G’$이 생긴다. 즉 어떤 고정된 공리계도 산술의 모든 진리를 담을 수 없다는 것이며, 수학이 끝없이 확장될 수 있다는 뜻으로 읽을 수도 있다.
정리
- 1차 논리는 완전하지만, 산술을 담은 공리계는 불완전하다.
- 핵심 도구: 괴델 수(수학을 수로) + 대각선 논법(자기 지시)
