괴델의 완전성 정리 문서 원본 보기

{{위키데이터 속성 추적}}
[[수리논리학]]에서 '''괴델의 완전성 정리'''(Gödel-完全性定理, {{llang|en|Gödel’s completeness theorem}})는 [[1차 논리]]에서 증명 가능한 명제의 집합은 [[구조 (논리학)|모형]]을 갖는다는 정리다. 즉, [[증명 이론]]으로 정의한 진리와 [[모형 이론]]으로 정의한 진리가 서로 일치한다.

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

== 정의 ==
부호수 <math>\sigma</math>에 대한 [[1차 논리]] 이론 (자유 변수를 갖지 않는 [[명제]]의 집합) <math>T</math>가 있다고 하자. 또한, <math>\phi</math>가 (자유 변수를 갖지 않는) <math>\sigma</math>-명제라고 하자. '''괴델의 완전성 정리'''에 따르면, 다음 두 조건이 서로 [[동치]]이다.<ref name="Marker">{{서적 인용 | last=Marker | first=David | title=Model theory: an introduction | publisher=Springer | 날짜=2002 | doi = 10.1007/b98860 | isbn = 978-0-387-98760-6 |총서=Graduate Texts in Mathematics|권=217|issn=0072-5285|zbl=1003.03034|언어=en}}</ref>{{rp|34}}<ref name="Enderton"/>{{rp|135}}
* ([[모형 이론]]적 진리) 모든 <math>\sigma</math>-[[구조 (논리학)|구조]] <math>M</math>에 대하여, 만약 <math>M\models T</math>라면 <math>M\models\phi</math>이다. 이는 보통 <math>T\models\phi</math>라고 쓴다.
* ([[증명 이론]]적 진리) <math>T\vdash\phi</math>
또한, '''괴델의 완전성 정리'''에 따르면 다음 두 조건이 서로 [[동치]]이다.
* (충족 가능성) <math>M\models T</math>인 <math>\sigma</math>-[[구조 (논리학)|구조]] <math>M</math>이 존재한다.
* (무모순성) <math>T\nvdash\bot</math>

== 증명 ==
괴델의 완전성 정리는 [[콤팩트성 정리]]로부터 유도할 수 있다. 1차 논리에서 콤팩트성 정리는 다음과 같이 쓸 수 있다.(<math>T</math>와 <math>\phi</math>는 위에서와 같은 의미이다)<ref name="Enderton"/>{{rp|142}}
# <math>T\models\phi</math>이면, <math>T_0\models\phi</math>인 [[유한 집합|유한]] 부분 집합 <math>T_0\subset T</math>가 존재한다.
# <math>T</math>의 모든 유한 부분집합이 충족 가능하면, <math>T</math> 역시 충족 가능하다.

첫 번째 정리의 증명은 다음과 같다.<ref name="Enderton"/>{{rp|142}}<math>T\vdash\phi</math>가  <math>T\models\phi</math>를 함의한다는 것은 [[건전성 정리]]이다. 반대로, <math>T\vdash\phi</math>를 가정하자. [[연역]] 과정은 유한하므로, <math>T_0\vdash\phi</math>인 유한 부분 집합 <math>T_0\subset T</math>가 존재한다. [[건전성 정리]]에 의해, 이는 <math>T_0\models\phi</math>를 함의한다. [[콤팩트성 정리]]에 의하여, <math>T\models\phi</math>이다.

두 번째 정리는 첫 번째 정리의 [[따름정리]]이다.<ref name="Enderton"/>{{rp|142}} <math>T</math>의 모든 유한 부분집합이 만족 가능하면, [[건전성 정리]]에 의해 모든 유한 부분 집합이 무모순이다. 그런데 [[연역]] 과정은 유한하므로, <math>T</math> 또한 첫 번째 명제에 의해 무모순이면 충족가능하다.

== 역사 ==
이 정리는 [[쿠르트 괴델]]이 1929년에 증명하였다. 이는 괴델의 1930년 박사학위 강연에 포함되었고, 1931년에 출판되었다.<ref name="Enderton">{{서적 인용|이름=Herbert B.|성=Enderton|제목=A mathematical introduction to logic|url=http://www.math.ucla.edu/~hbe/amil/|출판사=Academic Press|doi=10.1016/B978-0-08-049646-7.50001-1|판=2판|날짜=2001|isbn=978-0-12-238452-3|zbl=0992.03001|언어=en|확인날짜=2014년 11월 25일|보존url=https://web.archive.org/web/20141126034120/http://www.math.ucla.edu/~hbe/amil/|보존날짜=2014년 11월 26일|url-status=dead}}</ref>{{rp|145}}  [[괴델의 불완전성 정리]]와 함께 괴델의 가장 중요한 초기 업적으로 꼽힌다.

== 같이 보기 ==
* [[괴델의 불완전성 정리]]
* [[건전성 정리]]
* [[콤팩트성 정리]]
* [[뢰벤하임-스콜렘 정리]]

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=Gödel completeness theorem}}
* {{매스월드|id=GoedelsCompletenessTheorem|title=Gödel's completeness theorem}}
* {{매스월드|id=GeneralizedCompletenessTheorem|title=Generalized Completeness Theorem}}
* {{웹 인용|url=https://terrytao.wordpress.com/2009/04/10/the-completeness-and-compactness-theorems-of-first-order-logic/|이름=Terry|성=Tao|저자링크=테런스 타오|제목=
The completeness and compactness theorems of first-order logic|날짜=2009-04-10|웹사이트=What’s New|언어=en}}

{{전거 통제}}

[[분류:쿠르트 괴델의 작품]]
[[분류:수학기초론 정리]]
[[분류:메타논리학]]
[[분류:수리논리학]]
[[분류:모형 이론]]
[[분류:증명 이론]]