괴델의 완전성 정리

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

수리논리학에서, 괴델의 완전성 정리(Gödel-完全性定理, 영어: Gödel’s completeness theorem)는 1차 논리에서 증명 가능한 명제의 집합은 |모형을 갖는다는 정리다. 즉, 증명 이론으로 정의한 진리와 모형 이론으로 정의한 진리가 서로 일치한다.

이는 1차 논리의 가장 중요한 성질 가운데 하나이며, 고차 논리에서는 성립하지 않는다. 린드스트룀 정리에 따르면 1차 논리는 완전성과 콤팩트성을 만족하는 가장 강한 논리이다. 2차 논리 이상의 고차 논리에서는 완전성이 성립하지 않는다. 크립키 의미론을 이용하여 많은 경우 정규 양상 논리의 경우에도 완전성이 성립한다.

정의[편집]

부호수 \sigma에 대한 1차 논리 이론 (자유 변수를 갖지 않는 명제의 집합) T가 있다고 하자. 또한, \phi가 (자유 변수를 갖지 않는) \sigma-명제라고 하자. 괴델의 완전성 정리에 따르면, 다음 두 조건이 서로 동치이다.[1]:34[2]:135

또한, 괴델의 완전성 정리에 따르면 다음 두 조건이 서로 동치이다.

  • (충족 가능성) M\models T\sigma-구조 M이 존재한다.
  • (무모순성) T\nvdash\bot

증명[편집]

괴델의 완전성 정리는 콤팩트성 정리로부터 유도할 수 있다. 1차 논리에서 콤팩트성 정리는 다음과 같이 쓸 수 있다.(T\phi는 위에서와 같은 의미이다)[2]:142

  1. T\models\phi이면, G_0\models\phi유한 부분 집합 T_0\subset T가 존재한다.
  2. T의 모든 유한 부분집합이 충족 가능하면, T 역시 충족 가능하다.

첫 번째 정리의 증명은 다음과 같다. [2]:142T\models\phiT\vdash\phi를 함의한다는 것은 건전성 정리이다. 반대로, T\vdash\phi를 가정하자. 연역 과정은 유한하므로, T_0\vdash\phi인 유한 부분 집합 T_0\subset T가 존재한다. 건전성 정리에 의해, 이는 T_0\models\phi를 함의한다. 콤팩트성 정리에 의하여, T\models\phi이다.

두 번째 정리는 첫 번째 정리의 따름정리이다.[2]:142 T의 모든 유한 부분집합이 만족 가능하면, 건전성 정리에 의해 모든 유한 부분 집합이 무모순이다. 그런데 연역 과정은 유한하므로, T 또한 첫 번째 명제에 의해 무모순이면 충족가능하다.

역사[편집]

이 정리는 쿠르트 괴델이 1929년에 증명하였다. 이는 괴델의 1930년 박사학위 강연에 포함되었고, 1931년 출판되었다.[2]:145 괴델의 불완전성 정리와 함께 괴델의 가장 중요한 초기 업적으로 꼽힌다.

같이 보기[편집]

참고 문헌[편집]

  1. (영어) Marker, David (2002년). 《Model theory: an introduction》, Graduate Texts in Mathematics 217, ISSN 0072-5285. Springer. doi:10.1007/b98860. Zbl 1003.03034. ISBN 978-0-387-98760-6
  2. (영어) Enderton, Herbert B. (2001년). 《A mathematical introduction to logic》, 2판, Academic Press. doi:10.1016/B978-0-08-049646-7.50001-1. Zbl 0992.03001. ISBN 978-0-12-238452-3

바깥 고리[편집]