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