완전성 정리

논리학 Logics
{{{#!wiki style="margin: -0px -10px -5px; min-height: 28px" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -6px -1px -11px;"	<colbgcolor=#2ab5b5> 형식 논리	명제 논리( 논리 연산 · 삼단논법( 정언삼단논법) · 순환 논법) · 공리 · 진리치 · 술어 논리 · 논증( 논증의 재구성) · 모순 · 역설 · 논리적 오류( 논리적 오류/형식적 오류)
<colcolor=#000,#fff> 비표준 논리		직관 논리 · 양상논리 · 초일관 논리 · 다치논리( 퍼지논리) · 선형논리 · 비단조 논리
메타 논리		집합론 · 완전성 정리 · 불완전성 정리
비형식 논리	딜레마( 흑백논리)
	비형식적 오류	귀납적 오류 · 심리적 오류 · 언어적 오류 · 자료적 오류 · 양비론 · 진영논리 · 편견 및 고정관념 · 궤변 · 거짓 등가성
분야	수리철학 · 수리논리학
철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 · 수리논리학 둘러보기

}}}}}}}}} ||

수학기초론 Foundations of Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px"	다루는 대상과 주요 토픽
수리논리학	논리 · 논증{ 귀납논증 · 연역논증 · 귀추 · 유추} · 공리 및 공준 · 증명{ 증명보조기 · 자동정리증명 · 귀류법 · 수학적 귀납법 · 반증 · 더블 카운팅 · PWW} · 논리함수 · 논리 연산 · 잘 정의됨 · 조건문( 조각적 정의) · 명제 논리( 명제 · 아이버슨 괄호 · 역 · 이 · 대우) · 양상논리 · 술어 논리( 존재성과 유일성) · 형식문법 · 유형 이론 · 모형 이론
집합론	집합( 원소 · 공집합 · 집합족 · 곱집합 · 멱집합) · 관계( 동치관계 · 순서 관계) · 순서쌍( 튜플) · 서수( 하세 다이어그램 · 큰 가산서수) · 수 체계 · ZFC( 선택공리) · 기수( 초한기수) · 절대적 무한 · 모임
범주론	범주 · 함자 · 수반 · 자연 변환 · 모나드 · 쌍대성
계산가능성 이론	계산 · 오토마타 · 튜링 기계 · 바쁜 비버 · 정지 문제 · 재귀함수
정리
드모르간 법칙 · 대각선 논법 · 러셀의 역설 · 거짓말쟁이의 역설 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 집합-부분합 정리 · 퍼스의 항진명제 · 굿스타인 정리 · 완전성 정리 · 불완전성 정리( 괴델 부호화) · 힐베르트의 호텔 · 연속체 가설 · 퍼지 논리
기타
예비사항( 약어 및 기호) · 추상화 · 벤 다이어그램 · 수학철학
틀:논리학 · 틀:이산수학 · 틀:이론 컴퓨터 과학 · 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보		}}}}}}}}}

1. 개요2. 정리3. 주요 개념

3.1. 1차 논리3.2. '참'의 의미3.3. '증명 가능'의 의미

4. 수학적 함의

4.1. 콤팩트성 정리

5. 불완전성 정리와의 관련

1. 개요

完全性定理 / Completeness theorem

1차 논리에서 참인 명제는 모두 증명이 가능하다는 정리이다.

쿠르트 괴델이 1929년에 발표했다. 마찬가지로 괴델이 1931년에 증명한 불완전성 정리와 혼동하지 말 것. 불완전성 정리의 인지도가 압도적으로 높긴 하지만 완전성 정리 또한 그 수학적 의의가 상당히 크다. 완전성 정리의 증명으로 괴델은 박사 학위를 받았다.

2. 정리

1차 논리 이론 [math(T)]에 대하여 [math(T \vDash \phi)]라면, [math(T \vdash \phi)]가 성립한다.

괴델의 완전성 정리는 1차 논리의 의미론(semantics)과 통사론(syntax) 사이에 다리를 놓는 중요한 정리이다. [math(T \vDash \phi)]는 대략 "[math(T)]가 참이라면 [math(\phi)]가 참이다"를 표현하며, 이는 의미론적 진술이다. 한편 [math(T \vdash \phi)]는 대략 "[math(T)]로부터 [math(\phi)]를 증명할 수 있다"를 표현하며, 이는 통사론적 진술이다. 즉, 완전성 정리는 1차 논리에서 참인 명제는 증명 가능하다는 정리이다.

나아가 [math(T \vdash \phi)]라면 [math(T \vDash \phi)]가 성립한다는 사실을 쉽게 보일 수 있다. 따라서 1차 논리에서 '참'과 '증명 가능'은 동치이다. 이것은 불완전성 정리와 모순되는 것처럼 보이지만 그렇지 않다. 괴델의 불완전성 정리는 자연수를 포함하는 수학 체계에서 '참'과 '증명 가능'은 동치가 아니라는 정리인데, 1차 논리만으로는 자연수를 정확하게 표현할 수 없다. 따라서 불완전성 정리가 상정하는 "자연수를 포함하는 수학 체계"는 완전성 정리의 적용 범위를 벗어나 있다. 자세한 설명은 불완전성 정리와의 관련 항목 참조.

3. 주요 개념

3.1. 1차 논리

1차 논리, 또는 술어 논리는 명제 논리에서 사용하는 [math(\land)](그리고), [math(\lor)](또는), [math(\lnot)](부정), [math(\rightarrow)](...라면) 등의 논리 기호를 포함하여 변수, 함수, 술어 및 다음 두 양화사의 사용까지 허용하는 논리 체계이다.

[math(\exists x \; \phi)] : 어떤 [math(x)]에 대해 [math(\phi)]가 성립한다.
[math(\forall x \; \phi)] : 모든 [math(x)]에 대해 [math(\phi)]가 성립한다.

1차 논리의 '1차'라는 수식어는 양화사가 변수만 대상으로 할 수 있음을 의미한다. 즉, 다음 문장은 1차 논리에서 허용되지만,

[math(\exists x \; P(x))] (어떤 x에 대하여 P가 성립한다)

다음 문장은 양화사가 술어를 대상으로 하기 때문에 허용되지 않는다. 이런 문장까지 표현하고 싶다면 고차 논리를 사용해야 한다.

[math(\exists P \; P(x))] (x가 만족하는 어떠한 술어 P가 있다)

이렇듯 고차 논리는 1차 논리보다 표현력이 우월하지만 완전성 정리나 콤팩트성 정리 등 1차 논리가 지니는 근사한 성질들을 결여할 뿐더러 여러 철학적 문제를 일으키기 때문에 수학계에서 기피된다. 한편 명제 논리는 1차 논리에도 결여된 결정 가능성이라는 매우 좋은 성질을 지니지만 과도하게 표현력이 약하기 때문에 사용되지 않는다. 따라서 수학자들은 적당한 표현력과 꽤 근사한 성질을 가지는 1차 논리를 선호한다. 이런 면에서 1차 논리의 완전성을 보장하는 완전성 정리는 그 의의가 크다.

3.2. '참'의 의미

3.3. '증명 가능'의 의미

4. 수학적 함의

완전성 정리는 수학자들이 1차 논리를 선호하는 주된 이유 중 하나이다. 이로 인해 원래 고차 논리를 사용했던 여러 수학 체계들을 1차 논리로 번역하는 작업이 이루어졌다. 예를 들어 페아노 공리계의 5번 공리(귀납 공리)는 원래 고차 논리를 사용했지만, 현대 수학에서는 이를 1차 논리로 번역한 공리계를 사용한다. ZFC 공리계의 분류 공리 및 치환 공리도 1차 논리로 번역되었다. 고차 논리 공리를 1차 논리로 번역하는 것은 공리꼴(Axiom Schema)을 통해 가능하다.

4.1. 콤팩트성 정리

완전성 정리의 따름정리 중 하나는 콤팩트성 정리이다. 내용은 다음과 같다.

[math(\Gamma)]가 무한히 많은 공리의 집합이라고 하자. 임의의 [math(\Gamma)]의 유한한 부분집합이 모델을 가진다면, [math(\Gamma)]는 모델을 가진다.

풀어 설명하자면 이렇다. 유클리드의 다섯 공리를 만족하는 기하학 체계는 존재한다. 다름아닌 평면 기하학이다. 그러나 유클리드의 다섯 공리에 '삼각형의 세 내각의 합이 360도이다'라는 공리를 추가한 공리계를 만족하는 기하학 체계는 존재할 수 없다. 따라서 수학자들은 어떤 공리의 집합이 주어졌을 때, 그 공리들을 모두 만족하는 수학 체계가 존재하는지를 궁금해 하곤 한다. 특히 무한히 많은 공리들로 이루어진 공리계의 경우 이 질문은 답하기 까다롭다.

콤팩트성 정리는 이 질문에 답하는 한 가지 방법을 제공한다. 어떤 무한 공리계 Γ가 주어졌을 때, 이 공리계의 유한 부분집합 Δ를 임의로 상정한다. 만약 Δ를 만족하는 수학 체계가 항상 존재한다면, Γ를 만족하는 수학 체계 또한 존재함을 보장할 수 있다.

콤팩트성 정리는 매우 강력하다. 특히 무한소를 추가한 실수 체계가 무모순적이라는 사실을 보이는 데 사용할 수 있다.