불완전성 정리
위키백과 ― 우리 모두의 백과사전.
괴델의 불완전성 정리(Gödel's incompleteness theorems)는 1931년 쿠르트 괴델이 증명한 두 개의 정리로, 자연수를 포함하는 수학의 형식화에 대한 한계를 증명했다. 정리에 따르면, 자연수의 이론을 포함하며 모순이 없는 모든 공리계에는 참이지만 증명될 수 없는 명제가 존재하며, 또한 그 공리계는 자신의 무모순성을 증명할 수 없다.
이 정리는 수학의 체계를 완전하고 모순이 없는 공리계로 형식화하려는 힐베르트의 계획의 실패를 알리는 것으로 인식된다. 보다 구체적으로는, 이는 힐베르트의 두번째 문제에 대한 부정적인 해답으로 볼 수도 있다.
제1 불완전성 정리
괴델의 제1 불완전성 정리의 내용은 다음과 같다:
- 산술적으로 참인 명제를 증명할 수 있는 임의의 무모순인 계산가능한 가산 이론에 대해, 참이지만 이론 내에서 증명할 수 없는 산술적 명제를 구성할 수 있다. 즉, 산술을 표현할 수 있는 이론은 무모순인 동시에 완전할 수 없다.
여기에서 "이론"은 명제들의 무한집합으로, 여기에 속하는 것들 중 일부는 증명 없이 사실인 것으로 취급되는 공리이며 나머지는 공리들로부터 유도되는 정리이다. "(이론 내에서) 증명할 수 있는" 명제란 공리에 1차 논리를 적용하여 유도될 수 있는 것을 말한다. 이론 내에서 모순된 명제가 증명될 수 없을 경우 이를 무모순이라 한다. "구성할 수 있다"는 것은 이론 내에서 해당 명제를 실질적으로 제시할 수 있는 과정이 존재함을 말한다. 또한 여기에서 "산술"은 자연수의 덧셈과 곱셈만으로 이루어져 있으며, 이 정리의 결과로서 존재하는 참이지만 증명 불가능한 산술적 명제를 해당 이론의 "괴델 명제"라 한다.
제2 불완전성 정리
괴델의 제2 불완전성 정리의 내용은 다음과 같다:
- 공리로부터 출발한 산술체계가 무모순인지의 여부 자체가 참 또는 거짓인지 결정할 수 없다.
