괴델의 불완전성 정리 (Godel's Incompleteness Theorems)
한 줄 정의: 산술을 담은 무모순 형식체계에는 증명도 반증도 불가능한 명제가 존재합니다.
쉽게 풀면
자연수의 산술을 표현할 수 있을 만큼 충분히 강하고 모순이 없는 공리체계를 만들면, 그 체계 안에서 참이지만 증명할 수 없는 명제가 반드시 생깁니다. 이것이 제1 불완전성 정리입니다. 제2 정리는 한 걸음 더 나아가, 그런 체계는 자기 자신이 모순 없음을 스스로 증명할 수 없다고 말합니다.
왜 중요한가
모든 수학을 하나의 공리체계로 완결하려던 힐베르트의 계획이 원리적으로 불가능함을 보인 20세기 논리학의 분수령입니다. 계산 가능성의 한계를 다루는 튜링의 결과와 함께 형식체계의 본질적 제약을 규정하여, 논리학과 이론전산 전반에 기준점을 제공합니다.
논문에서는 이렇게 쓰입니다
"해당 체계가 산술을 해석할 수 있으므로 괴델의 불완전성 정리에 따라 결정 불가능한 명제가 존재한다."
조금 더 깊게 보면
증명의 핵심은 괴델 번호 매기기로, 논리식과 증명을 자연수로 부호화하여 체계가 자기 자신에 관해 말할 수 있게 만드는 것입니다. 그다음 나는 증명될 수 없다는 취지의 명제를 구성하는데, 이 자기참조 구조는 칸토어 대각선 논법과 같은 계열입니다. 정리는 체계가 무모순이고 공리가 기계적으로 열거 가능하며 산술을 충분히 표현할 수 있다는 조건 아래에서만 성립합니다.
주의할 점
정리가 말하는 것은 특정 조건을 만족하는 형식체계의 한계이지, 수학이 신뢰할 수 없다거나 인간 지성이 기계를 능가한다는 주장이 아닙니다. 그런 철학적 확대 해석은 정리의 내용과 구별해야 합니다.