(+)분류 : 가져온 문서/오메가
Incompleteness Theorem
괴델이 발표한 수리논리학의 주요 정리 중 하나로, 충분히 강력한 형식적 체계 내의 모든 진리를 알 수 있는 방법은 없다는 내용을 담고 있다.
1. 진술 ✎ ⊖
우선 괴델의 불완전성 정리를 서술하는 데 필요한 용어들을 몇 개 소개하자. 어떤 이론이 일관되었다는 것은 그 이론 내에서 와 가 동시에 증명되지 않는다는 것을 말한다. 그리고 어떤 이론이 완전하다는 것은 그 이론 내의 모든 명제가 참 혹은 거짓이라는 것, 즉 이거나 인 것을 말한다. 그리고 어떤 이론이 효율적으로 생성 가능하다는 것은 그 이론의 공리들의 집합이 재귀 열거 집합이란 것, 즉 주어진 이론 내에서 서술되는 명제들을 모두 나열했을 때 그 명제가 공리인지 아닌지 체크해서 그 명제가 공리이면 이를 출력해내는 프로그램이 존재한다는 것을 말한다. (이 때 그 프로그램이 끝날 필요는 없다.)
괴델의 불완전성 정리는 두 가지가 있는데, 이 둘을 각각 쓰자면 다음과 같다.
괴델의 제2 불완전성 정리는 몇몇 명제가 그 이론 내에서 결정 불가능임을 보일 때 이용된다.
위 두 정리에서 제시된 세 가지 조건 중에서 하나라도 만족하지 않으면 괴델의 정리는 유도되지 않는다.
페아노 공리 체계와 체르메로-프랜켈 공리 체계는 괴델의 정리에서 요구하는 세가지 조건을 만족한다.
괴델의 불완전성 정리는 두 가지가 있는데, 이 둘을 각각 쓰자면 다음과 같다.
- 괴델의 제1 불완전성 정리 일관되고 완전하며 산술을 포함하는 형식 체계는 효율적으로 생성 가능하지 않다.
- 괴델의 제2 불완전성 정리 : 가 산술을 포함하고 효율적으로 생성 가능하면, 가 일관되었단 사실을 내에서 증명할 수 없다.
괴델의 제2 불완전성 정리는 몇몇 명제가 그 이론 내에서 결정 불가능임을 보일 때 이용된다.
위 두 정리에서 제시된 세 가지 조건 중에서 하나라도 만족하지 않으면 괴델의 정리는 유도되지 않는다.
페아노 공리 체계와 체르메로-프랜켈 공리 체계는 괴델의 정리에서 요구하는 세가지 조건을 만족한다.
2. 오해 ✎ ⊖
많은 사람들은 괴델의 불완전성 정리가 '임의의 일관된 이론은 완전하지 않다'고 해석하는데, 이는 오류이다. 임의의 일관된 이론의 완비화가 엄연히 존재한다. 가 이론 의 모형이라 하면, ($mathfrak{A}$에서 참이 되는 모든 문장을 모은 집합)는 의 완비화이다. 하지만, 만약 $T$가 일관되었으면서 산술을 포함한다면, 그렇게 완비화된 이론을 효율적으로 공리화하는 방법은 존재하지 않는다.
