13.10 명제 논리 완전성 정리의 증명 개요

1. 절의 학술적 목표

본 절은 명제 논리 완전성 정리의 증명 개요를 학술적으로 검토하는 것을 목표로 한다. 완전성 정리의 증명은 건전성 정리의 증명보다 더 정교한 기법을 요구하며, 주로 극대 일관 집합의 구성과 만족 가능성 확립의 전략을 사용한다. 본 절은 증명의 전체 구조, 대우 형태의 재정식화, 극대 일관 집합의 구성, 해석의 구성, 만족 가능성의 증명, 대안적 증명 전략, 학술적 의의를 체계적으로 정리한다.

2. 증명의 전체 구조

명제 논리 완전성 정리의 증명은 다음과 같은 전체 구조를 가진다. 첫째, 증명 목표는 “Γ ⊨ A이면 Γ ⊢_L A이다”(강한 완전성)이다. 둘째, 증명의 기본 전략은 대우 형태 “Γ ⊬_L A이면 Γ ⊭ A이다“를 증명하는 것이며, 이는 “Γ ∪ {¬A}가 일관적이면 Γ ∪ {¬A}가 만족 가능하다“로 재정식화된다. 셋째, 증명의 핵심 단계는 일관된 명제 집합을 극대 일관 집합으로 확장하고(린덴바움 보조정리), 이 극대 일관 집합에서 진리 할당을 구성하여 만족 가능성을 확립하는 것이다. 넷째, 이 결과로부터 원래의 완전성 정리가 도출된다. 이러한 구조는 헨킨 스타일 완전성 증명의 표준적 형태이다(Henkin, 1949).

3. 대우 형태의 재정식화

완전성 정리의 증명은 대우 형태의 재정식화로부터 시작된다. 원래의 정리 “Γ ⊨ A이면 Γ ⊢_L A이다“의 대우는 “Γ ⊬_L A이면 Γ ⊭ A이다“이다. 후자의 진술은 “Γ로부터 A가 증명 가능하지 않으면 Γ의 모든 원소가 참이지만 A가 거짓인 어떤 해석이 존재한다“와 동등하다. 이는 다시 “Γ ∪ {¬A}가 일관적이면 Γ ∪ {¬A}가 만족 가능하다“로 재정식화된다. 이러한 재정식화는 증명의 방향을 “일관성에서 만족 가능성으로“의 함의로 전환하며, 구성적 증명의 출발점을 제공한다(Henkin, 1949).

4. 극대 일관 집합의 정의

극대 일관 집합(maximal consistent set)은 완전성 증명의 핵심 개념이다. 명제 집합 Δ가 극대 일관적이라는 것은 다음의 두 조건을 만족함을 의미한다. 첫째, Δ는 일관적이다(Δ ⊬_L ⊥). 둘째, Δ는 극대적이다(Δ에 속하지 않는 임의의 명제 A를 추가하면 Δ ∪ {A}가 일관적이지 않게 된다). 극대 일관 집합은 모든 명제 A에 대하여 A 또는 “¬A“를 포함하는 집합이며, 논리 연산에 대하여 닫혀 있다. 이러한 집합은 완전성 증명에서 해석(진리 할당)의 구성에 사용된다(van Dalen, 2013).

5. 린덴바움 보조정리

완전성 증명의 첫 단계는 린덴바움 보조정리(Lindenbaum’s lemma)의 확립이다. 린덴바움 보조정리는 “임의의 일관된 명제 집합 Γ는 극대 일관 집합 Δ로 확장될 수 있다(Γ ⊆ Δ)“를 주장한다. 이 보조정리의 증명은 다음과 같이 진행된다. 첫째, 명제 언어의 모든 명제를 열거한다(A₁, A₂, …). 둘째, Γ₀ = Γ로 시작하여, 각 단계 n에서 “Γₙ ∪ {Aₙ}가 일관적이면 Γₙ₊₁ = Γₙ ∪ {Aₙ}, 그렇지 않으면 Γₙ₊₁ = Γₙ“으로 정의한다. 셋째, Δ = ∪_n Γₙ로 정의한다. 이 Δ는 Γ를 포함하는 극대 일관 집합이다. 린덴바움 보조정리는 완전성 증명의 기본 도구이다(Lindenbaum & Tarski, 1936).

6. 극대 일관 집합의 성질

극대 일관 집합 Δ는 다음과 같은 주요 성질을 가진다. 첫째, 임의의 명제 A에 대하여 A ∈ Δ 또는 ¬A ∈ Δ 중 정확히 하나가 성립한다. 둘째, “A ∨ B ∈ Δ ⟺ A ∈ Δ 또는 B ∈ Δ“가 성립한다. 셋째, “A ∧ B ∈ Δ ⟺ A ∈ Δ 그리고 B ∈ Δ“가 성립한다. 넷째, “A → B ∈ Δ ⟺ A ∉ Δ 또는 B ∈ Δ“가 성립한다. 이러한 성질은 극대 일관 집합의 구조가 진리 할당의 구조와 정확히 일치함을 보여 주며, 해석의 구성에서 핵심적 역할을 한다(Henkin, 1949).

7. 해석의 구성

극대 일관 집합 Δ로부터 해석 I를 다음과 같이 구성한다. 각 명제 변항 P에 대하여 “I(P) = T이면 P ∈ Δ, I(P) = F이면 P ∉ Δ“로 정의한다. 이렇게 구성된 해석 I는 Δ의 모든 원소가 참이 되는 해석이다. 구체적으로, 복합 명제에 대한 I의 값은 명제 변항의 값과 논리 연산자의 진리표로부터 계산되며, 이 값이 극대 일관 집합의 성질에 의하여 명제의 Δ 소속성과 일치한다. 이러한 해석의 구성은 완전성 증명의 핵심 단계이다(Henkin, 1949).

8. 만족 가능성의 증명

해석의 구성 이후 완전성 증명은 “Δ의 모든 원소가 해석 I에서 참이다“를 증명한다. 이 증명은 명제의 구조에 대한 귀납법으로 수행된다. 기저 단계: 명제 변항의 경우, I의 정의에 의하여 “P ∈ Δ ⟺ I(P) = T“가 성립한다. 귀납 단계: 복합 명제의 경우, 귀납 가정과 극대 일관 집합의 성질로부터 “복합 명제가 Δ에 속함 ⟺ I에서 참이다“가 성립한다. 이 증명은 Δ의 모든 원소가 I에서 참임을 확립하며, 따라서 Δ는 만족 가능하다. Γ ⊆ Δ이므로 Γ도 만족 가능하며, 이는 원래 증명 목표를 완성한다(van Dalen, 2013).

9. 증명의 결론 도출

만족 가능성의 증명이 완료되면 완전성 정리의 결론이 도출된다. 증명의 전체 논리는 다음과 같다. Γ ⊨ A라고 가정한다. 대우를 증명하기 위하여 Γ ⊬_L A라고 가정한다. 그러면 Γ ∪ {¬A}는 일관적이며, 린덴바움 보조정리에 의하여 극대 일관 집합 Δ로 확장된다. Δ로부터 해석 I를 구성하면 Δ의 모든 원소가 I에서 참이며, 따라서 Γ의 모든 원소와 “¬A“가 I에서 참이다. 그러나 이는 “Γ의 모든 원소가 참이지만 A가 거짓인 해석 I가 존재함“을 의미하며, 이는 “Γ ⊨ A“와 모순된다. 따라서 “Γ ⊢_L A“가 성립해야 한다(Mendelson, 2015).

10. 대안적 증명 전략

명제 논리의 완전성 정리는 헨킨 스타일 증명 외에도 다른 전략으로 증명될 수 있다. 포스트(Emil Post)의 1921년 증명은 진리표 방법에 기반한다. 이 증명은 타당한 명제에 포함된 명제 변항의 수에 대한 귀납법으로 진행된다. 구체적으로, n개의 명제 변항을 포함하는 타당한 명제가 증명 가능함을 보이기 위하여, n-1개의 명제 변항을 포함하는 명제의 타당성과 증명 가능성의 관계를 활용한다. 이 방법은 명제 논리에 특화된 증명이며, 1차 술어 논리와 같은 더 복잡한 체계로의 직접적 확장은 어렵다. 헨킨 스타일 증명은 더 일반적이며, 다양한 논리 체계에 적용된다(Post, 1921).

11. 완전성 증명 개요의 학술적 의의

완전성 정리 증명 개요의 학술적 의의는 다음과 같이 정리된다. 첫째, 그것은 완전성 정리의 엄밀한 수학적 근거를 제공한다. 둘째, 그것은 극대 일관 집합의 구성과 해석의 구성이라는 메타이론적 증명의 핵심 기법을 제시한다. 셋째, 그것은 1차 술어 논리를 포함하는 다양한 논리 체계의 완전성 증명의 모범이 된다. 넷째, 그것은 일관성과 만족 가능성의 관계에 대한 형식적 분석을 제공한다. 다섯째, 그것은 학습자가 메타이론적 증명의 정교한 구조를 이해하는 데 기여한다. 이러한 의의는 완전성 증명 개요가 메타논리학 학습의 핵심 내용임을 보여 준다(van Dalen, 2013).

12. 본 절의 결론적 정리

명제 논리 완전성 정리의 증명은 대우 형태의 재정식화 “일관된 명제 집합은 만족 가능하다“로부터 시작한다. 증명의 핵심 단계는 다음과 같다. 첫째, 린덴바움 보조정리에 의하여 임의의 일관된 명제 집합이 극대 일관 집합으로 확장된다. 둘째, 극대 일관 집합의 주요 성질(임의의 명제 A에 대하여 A 또는 ¬A 중 정확히 하나를 포함, 논리 연산에 대한 일관된 행동)이 확립된다. 셋째, 극대 일관 집합으로부터 해석이 구성된다. 넷째, 명제의 구조에 대한 귀납법으로 극대 일관 집합의 모든 원소가 구성된 해석에서 참임이 증명된다. 다섯째, 이로부터 원래 집합의 만족 가능성이 도출되고, 완전성 정리의 대우가 확립된다. 대안적 증명 전략으로 포스트의 진리표 기반 증명이 있다. 학습자는 완전성 증명의 전체 구조, 대우 형태의 재정식화, 극대 일관 집합의 구성과 성질, 해석의 구성, 만족 가능성의 증명을 정확히 이해해야 한다.

13. 출처

• Post, E. L. (1921). Introduction to a general theory of elementary propositions. American Journal of Mathematics, 43(3), 163–185.
• Lindenbaum, A., & Tarski, A. (1936). Über die Beschränktheit der Ausdrucksmittel deduktiver Theorien. Ergebnisse eines mathematischen Kolloquiums, 7, 15–22.
• Henkin, L. (1949). The completeness of the first-order functional calculus. The Journal of Symbolic Logic, 14(3), 159–166.
• van Dalen, D. (2013). Logic and Structure (5th ed.). Berlin: Springer.
• Mendelson, E. (2015). Introduction to Mathematical Logic (6th ed.). Boca Raton: CRC Press.

14. 버전

• 문서 버전: 1.0
• 작성 기준일: 2026-04-15