Completeness Theorem
수학에서 쓰이는 공리 (Axiom) 들은 오늘날까지 알려진 것 외에 더 있을 수 없는가? 즉,아직도 발견하지 못한 수학의 원리가 남아 있어서 장차 새로이 발견될 여지가 남아 있을 것인가? ..... 집합론이 수학의 기본 이론이기 때문에 앞의 물음은 "집합론의 공리는 지금까지 알려진 것 외에 또 더 없을까?" 로 할 수 있다. 이를 다시 집합론과 논리학으로 나누면 다음과 같이 정리할 수 있다. 첫째로, 논리학의 기본 원리 즉, 논리학의 기본 법칙은 현재까지 알려진 것 외에 더 없을까? 둘째로, 집합론의 기본 원리 즉 공리는 지금까지 알려진 것 외에 없을까? 즉, 현재의 집합론은 완전(complete)한가?
이 두 물음 모두에 대해 괴델은 그 답을 우리에게 제시해 주고 있다. 첫번째 물음에 대해 괴델은 24세 때 빈 대학교에 제출한 학위 논문에서 술어논리의 완전성(completeness)정리를 통해 긍정적으로 답하였다. 즉, 그의 완전성 정리에 따르면 "술어논리는 완전하다. 그러므로 술어논리 체계에는 지금 우리가 알고 있는 원리 외에는 장차 더 새로이 발견될 것이 없다." 바꿔 말하면, 앞으로 기본 원리인 술어 논리학에서의 공리는 영원히 새로이 발견될 것이 없다는 뜻이 된다. 여기서 어떤 이론체계가 완전 (complete) 하다는 뜻은 그 체계에서 참인 명제는 반드시 공리로 부터 연역 (증명) 된다 (즉, 정의가 된다) 는 뜻이다. 반대로, 어떤 이론체계가 불완전하다 (incomplete) 는 뜻은 그 체계에 있어 참인 명제가 그 체계의 공리로부터 연역되지 않은 경우가 있다는 뜻이다. ...... 다음 두번째 물음에 대해서는 괴델이 부정적인 답을 얻었다. 그 내용은 "현재의 산술체계가 무모순하면 그 체계는 불완전하다"로 정리할 수 있다. 즉, "그 체계의 어떠한 명제가 참이지만, 그 명제와 그것의 부정명제 모두가 증명되지 않은 명제가 존재한다."는 뜻이다. 사실은 이 정리를 제1불완전성정리 라고 한다.
논리학과 수학 , 술어논리의 완전성 정리 : 요시나가 요시마사 : ...... Kurt Gödel 은 1930 년에 완전성 정리 (Completeness Theorem) 의 증명을, 1931 년에 불완전성 정리 (Incompleteness Theorem) 의 증명을 발표하였다. 그러나 이것은 모순되는 것은 아니다. 왜냐하면 전자는 논리학 (제 1 계 술어논리) 의 형식적 체계에 대해서, 후자는 수학 (페아노의 산술의 공리계를 포함하는 무모순인 공리계) 의 형식적 체계에 대한 정리이고 양자는 근본적으로 상이한 것에 대한 언급이었기 때문이다 ...... 괴델의 완전성 정리는 논리학의 형식적 체계에 대해서 증명된 사항이다. 우리들이 사용하고 있는 논리학의 체계는 완전하다. 즉 '논리적으로 올바른' 명제라면 어떠한 것이라도 그 체계 내에서 '증명가능' 하다 라는 것이다. 우리들의 "상식적" 인 논리적 직관에는 초수학적인 뒷받침이 있었던 것이다 라고 말해도 될 것이다.
논리의 다음으로는 수학이 문제로 되는데 여기서는 '수학적으로 올바르다' 는 것이 '논리적으로 올바르다' 는 것과는 반드시 일치하는 것은 아니다. 논리적인 올바름이란 어떠한 대상에 대해서도 적용되는 추론의 올바름에 대한 것을 말한다. 예컨대 「A 이면 A」가 그 좋은 예이고 A 가 진실이든 허위이든 이 추론 바로 그것은 올바르다고 말할 수 있다. 이러한 추론을 항진명제 (Tautology) 라 부른다. 토톨러지는 일상용어로는 '동어반복' 이라고 번역되어 있다.
수학적인 올바름은 이것과는 달리 사항의 진위가 추궁된다. 즉 수학에 있어서의 명제는 수학적인 내용을 갖는 이상 원리적으로는 진위가 미리 결정되어 있을 것이다 (다만 소위 '자유변수' 를 갖지 않는 경우). 그래서 수학의 형식적 체계에 대한 완전성의 요청이란 '모든 참된 명제가 그 체계 내에서 증명될 수 있는 것' 으로 된다. 어쩐지 자명한 것으로 생각되나 그것이 자명하기는 커녕 잘못된 것이라는 것을 증명해 버린 것이 괴델의 불완전성 정리였던 것이다 ......
Wikipedia : Gödel's completeness theorem : 1929 년에 Kurt Gödel 이 증명한 수리논리학에서의 기본 정리이다. 가장 일반적으로 말하자면, 일차술어계산에서 모든 universally valid formula 는 증명될 수 있다는 것이다. 논리적 공식이 모든 가능한 영역에서 모든 가능한 해석 (그 영역에서 공식에 사용된 non-constant symbols 의 해석) 이 참일 경우를 universally valid 라고 부른다. .....