13.11 극대 일관 집합의 구성

13.11 극대 일관 집합의 구성

1. 절의 학술적 목표

본 절은 명제 논리에서 극대 일관 집합(maximal consistent set)의 구성을 학술적으로 검토하는 것을 목표로 한다. 극대 일관 집합은 완전성 정리의 증명에서 핵심적 역할을 하는 개념이며, 헨킨 스타일 완전성 증명의 기본 도구이다. 본 절은 극대 일관 집합의 정의, 주요 성질, 구성 방법, 명제 열거의 역할, 집합의 성질에 관한 증명, 학술적 의의를 체계적으로 정리한다.

2. 극대 일관 집합의 학술적 정의

명제 집합 Δ가 극대 일관 집합이라는 것은 다음의 두 조건을 동시에 만족함을 의미한다. 첫째, Δ는 일관적이다. 즉, Δ로부터 모순(⊥)이 도출될 수 없다(Δ ⊬_L ⊥). 둘째, Δ는 극대적이다. 즉, Δ의 부분 집합이 아닌 임의의 명제 집합은 일관적이지 않다. 형식적으로, Δ ⊊ Γ이면 Γ는 일관적이지 않다. 또는 동등하게, 임의의 명제 A에 대하여 “A ∉ Δ이면 Δ ∪ {A}가 일관적이지 않다“가 성립한다. 이러한 정의는 Δ가 일관성을 유지하면서 더 이상 확장될 수 없는 집합임을 보장한다(Henkin, 1949).

3. 극대 일관 집합의 기본 성질

극대 일관 집합 Δ는 다음과 같은 기본 성질을 가진다. 첫째, 임의의 명제 A에 대하여 A ∈ Δ 또는 ¬A ∈ Δ 중 정확히 하나가 성립한다. 둘째, Δ는 구문론적 귀결 관계에 대하여 닫혀 있다. 즉, Δ ⊢_L A이면 A ∈ Δ이다. 셋째, Δ는 논리 연산자에 대하여 닫혀 있다. 예를 들어, “A ∧ B ∈ Δ ⟺ A ∈ Δ 그리고 B ∈ Δ“가 성립한다. 넷째, Δ는 모든 논리 정리를 포함한다. 이러한 성질은 극대 일관 집합이 완전한 “이론“의 구조를 가짐을 보여 준다(van Dalen, 2013).

4. 극대 일관 집합의 구성 방법

명제 논리에서 극대 일관 집합의 구성 방법은 다음과 같다. 주어진 일관된 명제 집합 Γ로부터 출발하여 극대 일관 집합 Δ로 확장한다. 구성 절차는 다음과 같다. 첫째, 명제 언어의 모든 명제를 열거한다(A₁, A₂, A₃, …). 이 열거는 명제 언어가 가산(countable)이기 때문에 가능하다. 둘째, Γ₀ = Γ로 초기화한다. 셋째, 각 단계 n에서 “Γₙ ∪ {Aₙ₊₁}가 일관적이면 Γₙ₊₁ = Γₙ ∪ {Aₙ₊₁}, 그렇지 않으면 Γₙ₊₁ = Γₙ“으로 정의한다. 넷째, Δ = ∪_{n=0}^∞ Γₙ로 정의한다. 이 Δ가 Γ를 확장하는 극대 일관 집합이다(Henkin, 1949).

5. 명제 열거의 역할

극대 일관 집합의 구성에서 명제 열거(enumeration of formulas)는 핵심적 역할을 한다. 명제 언어의 가산성(countability)은 명제를 자연수와 일대일로 대응시킬 수 있음을 의미하며, 이는 모든 명제를 체계적으로 하나씩 검토할 수 있게 한다. 명제의 열거는 구체적으로 다음과 같이 수행될 수 있다. 첫째, 명제 변항 P₁, P₂, … 를 가산 무한 집합으로 둔다. 둘째, 명제의 길이와 복잡도에 따라 명제를 순서대로 나열한다. 셋째, 동일한 길이와 복잡도의 명제들은 사전식 순서로 나열한다. 이러한 열거 방법은 명제 언어의 모든 명제가 어떤 단계에서 반드시 고려됨을 보장한다(Mendelson, 2015).

6. 일관성의 유지 증명

극대 일관 집합의 구성에서 각 단계 Γₙ의 일관성이 유지됨을 증명해야 한다. 증명은 귀납법으로 수행된다. 기저 단계: Γ₀ = Γ는 전제에 의하여 일관적이다. 귀납 단계: Γₙ이 일관적이라고 가정한다. 단계 n+1의 정의에 의하여 “Γₙ ∪ {Aₙ₊₁}가 일관적이면 Γₙ₊₁ = Γₙ ∪ {Aₙ₊₁}, 그렇지 않으면 Γₙ₊₁ = Γₙ“이다. 전자의 경우 정의에 의하여 Γₙ₊₁이 일관적이며, 후자의 경우 Γₙ₊₁ = Γₙ이 귀납 가정에 의하여 일관적이다. 따라서 모든 단계 Γₙ은 일관적이다(Henkin, 1949).

7. 합집합 Δ의 일관성

무한 합집합 Δ = ∪_{n=0}^∞ Γₙ의 일관성은 다음과 같이 증명된다. Δ가 일관적이지 않다고 가정하면, Δ로부터 모순(⊥)이 도출된다. 이 도출은 유한한 증명이며, 유한개의 명제만을 전제로 사용한다. 이 전제들은 모두 어떤 유한한 Γₙ에 포함되므로, Γₙ로부터도 모순이 도출된다. 이는 Γₙ이 일관적임에 모순된다. 따라서 Δ는 일관적이다. 이 증명은 증명의 유한성을 활용하며, 명제 논리의 기본 성질에 의존한다(van Dalen, 2013).

8. Δ의 극대성

Δ의 극대성은 다음과 같이 증명된다. 임의의 명제 A ∉ Δ를 고려한다. 명제의 열거에 의하여 A는 어떤 n에서 Aₙ로 나타난다. A ∉ Δ이므로 A ∉ Γₙ이며, 이는 “Γₙ₋₁ ∪ {Aₙ}가 일관적이지 않음“을 의미한다. 따라서 Δ ∪ {A}는 일관적이지 않다(Γₙ₋₁ ⊆ Δ이므로 Δ ∪ {A}는 Γₙ₋₁ ∪ {Aₙ}을 포함). 이는 Δ의 극대성을 증명한다. 즉, Δ에 포함되지 않은 어떠한 명제를 추가하여도 일관성이 깨진다(Henkin, 1949).

9. A ∈ Δ 또는 ¬A ∈ Δ의 증명

극대 일관 집합의 주요 성질 중 하나는 “임의의 명제 A에 대하여 A ∈ Δ 또는 ¬A ∈ Δ 중 적어도 하나가 성립함“이다. 이 성질의 증명은 다음과 같다. 가정으로 A ∉ Δ 그리고 ¬A ∉ Δ를 가정한다. 극대성에 의하여 Δ ∪ {A}와 Δ ∪ {¬A}가 모두 일관적이지 않다. 전자로부터 Δ ⊢ ¬A가 도출되고, 후자로부터 Δ ⊢ A가 도출된다. 그러나 이 경우 Δ ⊢ A ∧ ¬A이며, 이는 Δ의 일관성에 모순된다. 따라서 A ∈ Δ 또는 ¬A ∈ Δ 중 적어도 하나가 성립한다. 또한 일관성에 의하여 두 경우가 동시에 성립하지는 않으므로, 정확히 하나가 성립한다(Mendelson, 2015).

10. 구문론적 귀결 관계에 대한 닫힘

극대 일관 집합 Δ의 또 다른 주요 성질은 구문론적 귀결 관계에 대한 닫힘이다. 즉, “Δ ⊢_L A이면 A ∈ Δ“이다. 이 성질의 증명은 다음과 같다. Δ ⊢_L A를 가정한다. A ∉ Δ라고 가정하면, 극대성에 의하여 Δ ∪ {¬A}가 일관적이지 않다. 이는 Δ ⊢_L A(가정과 동일)와 Δ ⊢_L ¬A 중 후자가 성립함을 의미한다. 그러나 Δ ⊢_L A와 Δ ⊢_L ¬A는 Δ의 일관성에 모순된다. 따라서 A ∈ Δ이어야 한다. 이 성질은 극대 일관 집합이 완전한 이론의 구조를 가짐을 보여 준다(van Dalen, 2013).

11. 극대 일관 집합의 학술적 의의

극대 일관 집합 개념과 그 구성 방법의 학술적 의의는 다음과 같이 정리된다. 첫째, 그것은 완전성 정리 증명의 기본 도구를 제공한다. 둘째, 그것은 일관성과 만족 가능성의 관계를 형식적으로 규명한다. 셋째, 그것은 모델 이론의 기본 구성 기법이며, 1차 술어 논리의 완전성 증명으로도 확장된다. 넷째, 그것은 논리 체계와 집합론의 접점을 제공한다. 다섯째, 그것은 증명 이론과 모델 이론의 접점에서 중요한 개념이다. 이러한 의의는 극대 일관 집합이 메타논리학의 핵심 개념임을 보여 준다(Henkin, 1949).

12. 본 절의 결론적 정리

극대 일관 집합은 일관적이면서 더 이상 확장될 수 없는 명제 집합이며, 명제 논리의 완전성 정리 증명에서 핵심 도구이다. 극대 일관 집합의 구성 방법은 다음과 같다. 명제 언어의 모든 명제를 열거하고, 주어진 일관된 집합 Γ로부터 출발하여 각 단계에서 일관성을 유지하는 명제를 순차적으로 추가함으로써 무한 합집합 Δ를 구성한다. Δ의 일관성은 증명의 유한성으로부터 도출되며, 극대성은 명제 열거의 완전성에 의하여 보장된다. 극대 일관 집합 Δ는 “임의의 명제 A에 대하여 A ∈ Δ 또는 ¬A ∈ Δ 중 정확히 하나가 성립”, “구문론적 귀결 관계에 대한 닫힘”, “논리 연산자에 대한 닫힘” 등의 주요 성질을 만족한다. 극대 일관 집합의 구성 방법은 헨킨 스타일 완전성 증명의 기본 기법이며, 1차 술어 논리를 포함하는 다양한 체계로 확장된다. 학습자는 극대 일관 집합의 정의, 구성 방법, 주요 성질과 그 증명, 학술적 의의를 정확히 이해해야 한다.

13. 출처

  • 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