|
괴델의 불완전성 정리의 구조
다음 내용은 괴델의 불완전성 정리를 공부하는 전공학생들에게 아마 도움이 될 것입니다. 괴델 공부의 내용은 증명을 이해하는 것인데, 증명을 이해할 때 교과서를 봐서 어려운 것은 증명의 전체적인 흐름과 구조를 이해하는 것이지요. 다음 내용은 이에 도움이 될 것이라고 봅니다. 자세한 내용은 "계산가능성과 논리", "나, 아바타, 그리고 가상세계"(책세상, 2000) 등을 참조하세요. 괴델의 불완전성 정리란 무엇인가? - 제1 정리: 어떠한 형식체계이든 - 이 체계가 대부분의 수학체계에 의해 만족되는 아주 간단한 어떤 조건을 만족한다면 - 이 체계가 일관적(무모순적)인 한 이 체계 안에 그 체계에서 증명도 반증도 할 수 없는(결정불가능한) 문장이 적어도 하나 이상 존재한다. - 제2 정리: 첫번째 정리의 조건을 만족하는 어떠한 형식체계도 그 체계가 일관적인 한, 그 체계 내에서 주어진
공리와 규칙들만으로는 그 일관성을 증명할 수 없다.
괴델 증명의 기본 발상: 거짓말쟁이 역설 크레타 사람이 말했다. "모든 크레타 사람은 거짓말쟁이이다." 그렇다면 이 말은 거짓말일까 참말일까?
괴델 증명의 기본 장치: 괴델수와 괴델 문장 괴델 증명의 출발점은 형식화된 논리(언어) 체계이다. 이 언어를 구성하는 모든 기호, 논리적, 증명 하나하나에 고유한 번호(괴델 수)를 지정한다. 여기서 논리식이란 기호를 규칙에 의해 하나로 묶은 것이다. 그리고 문장은 논리식이다. 괴델 수를 부여하는 방식은 소수가 무한히 많이 있다는 특성을 이용한다. 그리고 소수의 곱은 다시 소수로 분해된다는 것도 소수의 중요한 특성이다. 그리고는 괴델은 간단한 산술의 특성을 이용하여 "나는 증명될 수 없다"와 같은 문장을 구성한다. 이 문장은 자기 자신을 증명할 수 없는 논리적 형식을 갖는다. 기본 개념: 괴델 수를 각 논리식에 부여함으로써 복잡한 논리적 관계를 직접 분석하지 않고 이 분석을 산술을 통해서 명확히 드러내는 것이다.
제1정리의 증명 과정 1) '논리식 G는 증명 불가능하다'라는 메타 수학적 문장을 나타내는 논리식 G를 구성한다. 2) G의 부정(~G)이 증명 가능할 때, 그리고 오직 그 때에만 G가 증명 가능하게 된다. :왜냐하면, ~G가 증명가능하다는 것은 "G는 증명 불가능하지는 않다"가 증명가능하다는 것을 의미하기 때문이다. 3) G가 증명할 수 없는 식이며 동시에 참인 논리식임을 제시한다. 4) G가 참이지만 증명불가능하므로, 산술체계는 불완전하다는 결론(제1정리)을 도출한다. <설명> 논리식 G는 이런 뜻이다. "나는 증명불가능한 문장이다". 만약 이 문장이 증명가능하다면 G의 부정, 즉 ~G(나는 증명될 수 있다)가 증명되어야 한다. 즉 G가 틀렸다는 것이 증명되어야 하는 것이다. 이상의 내용을 정리하면 이렇게 된다. 즉, G가 증명가능하다면 ~G가 증명되어야 한다. 이것은 서로 모순적이다. 그러므로 G는 증명불가능하다. 그런데 그것이 G의 내용이므로 G는 참이게 된다. 즉 G는 증명불가능하면서 참인 문장인 것이다. 그리고 이 문장 G가 산술체계에서 구성될 수 있으므로 산술체계는 불완전하게 된다.
제2정리의 증명 과정(제1정리에서 출발) 1) 먼저 논리식 H를 구성한다. H는 "산술체계가 일관적이다"라는 문장이다. 2) "H이면 G이다"가 증명가능하다는 것을 보인다. 3) H가 증명가능하지 않다는 것을 증명한다. 4) 이로부터 제2정리를 얻는다.
|
<철학, 지식이 아닌 지혜> |
처음으로
