괴델의 불완전성 정리 (편집)

[[분류:가져온 문서/오메가]]
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]])]

(임시 저장) (임시 저장 불러오기)

(↪️) (💎) (🛠️) (추가)

[[분류:가져온 문서/오메가]]
Incompleteness Theorem

괴델이 발표한 수리논리학의 주요 정리 중 하나로, 충분히 강력한 형식적 체계 내의 모든 진리를 알 수 있는 방법은 없다는 내용을 담고 있다.

괴델의 제2 불완전성 정리는 몇몇 명제가 그 이론 내에서 결정 불가능임을 보일 때 이용된다.

== 영상 ==
[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]])]

비로그인 상태입니다. 편집한 내용을 저장하면 지금 접속한 IP가 기록됩니다.

편집을 전송하면 당신은 이 문서의 기여자로서 본인이 작성한 내용이 CC BY 4.0에 따라 배포되고, 기여한 문서의 하이퍼링크나 URL로 저작자 표시가 충분하다는 것에 동의하는 것입니다.