Incompleteness Theorem

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

목차
1. 진술
2. 오해
3. 영상

1. 진술 ✎

우선 괴델의 불완전성 정리를 서술하는 데 필요한 용어들을 몇 개 소개하자. 어떤 이론이 일관되었다는 것은 그 이론 내에서 \phi와 \lnot\phi가 동시에 증명되지 않는다는 것을 말한다. 그리고 어떤 이론이 완전하다는 것은 그 이론 내의 모든 명제가 참 혹은 거짓이라는 것, 즉 T\vdash \phi이거나 T\vdash\lnot\phi인 것을 말한다. 그리고 어떤 이론이 효율적으로 생성 가능하다는 것은 그 이론의 공리들의 집합이 재귀 열거 집합이란 것, 즉 주어진 이론 내에서 서술되는 명제들을 모두 나열했을 때 그 명제가 공리인지 아닌지 체크해서 그 명제가 공리이면 이를 출력해내는 프로그램이 존재한다는 것을 말한다. (이 때 그 프로그램이 끝날 필요는 없다.)

괴델의 불완전성 정리는 두 가지가 있는데, 이 둘을 각각 쓰자면 다음과 같다.
  • 괴델의 제1 불완전성 정리 일관되고 완전하며 산술을 포함하는 형식 체계는 효율적으로 생성 가능하지 않다.
  • 괴델의 제2 불완전성 정리 : T가 산술을 포함하고 효율적으로 생성 가능하면, T가 일관되었단 사실을 T 내에서 증명할 수 없다.

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

위 두 정리에서 제시된 세 가지 조건 중에서 하나라도 만족하지 않으면 괴델의 정리는 유도되지 않는다.
페아노 공리 체계와 체르메로-프랜켈 공리 체계는 괴델의 정리에서 요구하는 세가지 조건을 만족한다.

2. 오해 ✎

많은 사람들은 괴델의 불완전성 정리가 '임의의 일관된 이론은 완전하지 않다'고 해석하는데, 이는 오류이다. 임의의 일관된 이론의 완비화가 엄연히 존재한다. \mathfrak{A}가 이론 T의 모형이라 하면, \mathrm{Th}\mathfrak{A} ($mathfrak{A}$에서 참이 되는 모든 문장을 모은 집합)는 T의 완비화이다. 하지만, 만약 $T$가 일관되었으면서 산술을 포함한다면, 그렇게 완비화된 이론을 효율적으로 공리화하는 방법은 존재하지 않는다.

3. 영상 ✎




이 문서의 내용 중 전체 또는 일부는 오메가에서 가져왔으며 CC BY-NC-SA 3.0에 따라 이용할 수 있습니다.

관련 문서




(돌아가기)
(임시 저장) (임시 저장 불러오기)


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



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