완전성 정리

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도이다'라는 공리를 추가한 공리계를 만족하는 기하학 체계는 존재할 수 없다. 따라서 수학자들은 어떤 공리의 집합이 주어졌을 때, 그 공리들을 모두 만족하는 수학 체계가 존재하는지를 궁금해 하곤 한다. 특히 무한히 많은 공리들로 이루어진 공리계의 경우 이 질문은 답하기 까다롭다.

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

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

5. 불완전성 정리와의 관련[편집]

---

[각주]