괴델의 완전성 정리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

괴델의 완전성 정리(독일어: Gödelscher Vollständigkeitssatz 괴델셔 폴슈텐디히카이츠자츠[*], Gödel's completeness theorem, -完全性定理), 또는 괴델의 완비성 정리(-完備性定理)는 쿠르트 괴델1929년 처음으로 증명한 수리논리학의 기초적인 정리 중의 하나이다. 괴델의 불완전성 정리와 함께 괴델의 가장 중요한 초기 업적으로 꼽힌다. 이 정리는 괴델의 1930년 박사학위 강연에 포함되었고, 1931년 출판되었다.[1]

이 정리는 일차 논리학의 연역 계산은 완비성(completeness)을 갖는다, 즉, 어떤 논리식이 의미론적으로 이면, 증명가능하다는 것을 의미한다. 이 정리의 내용은 간단하나 증명을 위해서는 상당히 길고 복잡한 논증이 필요하다. 역은 보다 쉽게 성립하는데, 이는 건전성 정리로 주어진다.

일차 논리학 외에 크립키 의미론을 이용하여 많은 경우 정규 양상 논리학의 완비성 역시 증명할 수 있다. 하지만 유명한 괴델의 불완전성 정리는 이 정리의 일반화가 쉽지 않음을 보여 주고 있다. 실제로, 린드스트룀 정리에 따르면 일차 논리학은 완비성과 컴팩트성을 만족하는 가장 강한 논리학 체계이다. 이차 논리학 이상의 고차 논리학에서는 완비성이 성립하지 않는다.

공식화[편집]

어떤 논리식들의 집합 G와 논리식 p에 대하여, 이 정리는 다음과 같이 두 명제로 표현할 수 있다.[2]

  1. G \vDash p 이면, G \vdash p 이다.
  2. G무모순이면 충족가능하다.

컴팩트성 정리와의 관계[편집]

이 정리를 통해 괴델은 일차 논리학에서의 컴팩트성 정리를 유도하여, 일차 논리학의 컴팩트성을 확보하였다. 일차 논리에서 컴팩트성 정리는 다음과 같이 쓸 수 있다.(G와 p는 위에서와 같은 의미이다)[3]

  1. G \vDash p 이면, 적당한 G의 유한 부분집합 G_0 이 존재하여 G_0 \vDash p 이다.
  2. G의 모든 유한 부분집합 G_0 가 충족가능하면, G도 충족가능하다.

첫 번째 명제의 증명은 다음과 같다. 이상의 완비성 정리에 의하면 G \vDash p 이면 G \vdash p 이다. 그런데 연역 과정은 유한하므로, G \vdash p 는 적당한 G_0 에 대하여 G_0 \vdash p 을 함의한다. 또 이것은 건전성 정리에 의해 G_0 \vDash p 를 함의한다.[3]

두 번째 명제의 증명도 유사하게 할 수 있다. G의 모든 유한 부분집합이 충족가능하면, 건전성 정리에 의해 모든 유한 부분집합이 무모순이다. 그런데 연역 과정은 유한하므로, G도 무모순이다. 완비성 정리에 의해 무모순이면 충족가능하므로, 원하는 결과를 얻는다.[3]

같이 보기[편집]

주석[편집]

  1. Herbert B. Enderton (2002), A mathematical introduction to logic, Academic Press(Elsevier), p.145.
  2. Ibid. , p.135.
  3. Ibid. , p.142.

참고 문헌[편집]

  • Herbert B. Enderton (2002), A mathematical introduction to logic, Academic Press(Elsevier)