본문 바로가기
Topos Uranos
한국어

콤팩트성 정리

요약

연역은 유한한 열이며 유한 개의 전제만 사용한다. 반면 논리식의 무한 집합의 충족은 단 하나의 진리값 할당이 무한히 많은 논리식에 동시에 값 11을 줄 것을 요구하며, 그 정의의 어디에도 유한한 부분을 살피는 것으로 충분하다는 말은 없다. 콤팩트성 정리는 그것으로 충분하다고 주장한다. 논리식의 집합이 충족 가능한 것은 그 유한 부분집합 각각이 충족 가능할 때 그리고 그때에만이다. 이 수업은 연역을 거치지 않고 직접적인 의미론적 논증으로 이를 증명한다. 변항 v1,v2,…v_1, v_2, \ldots의 값을 하나씩 고정하면서, 각 단계에서 집합의 모든 유한 부분집합이 이미 고정된 것을 따르는 할당에 의해 여전히 충족 가능하다는 불변량을 유지한다. 가능한 두 선택 중 어느 것도 이를 유지하지 못한다면 그 실패의 두 유한한 증인의 합집합이 앞의 불변량에 모순될 것이며, 마지막에 각 논리식은 유한 개의 변항만 가지므로 일치 보조정리에 의해 충족된다. 변항에는 번호가 붙어 있으므로 이 구성에는 선택 공리가 필요하지 않다. 콤팩트성으로부터 그 동치인 형태들(집합이 충족 불가능한 것은 어떤 유한 부분이 충족 불가능할 때 그리고 그때에만이고, 논리식이 집합의 귀결인 것은 어떤 유한 부분의 귀결일 때 그리고 그때에만이다)이 따라 나오고, 앞 수업의 유한 전제에 대한 완전성과 함께 강한 완전성이 따라 나온다. 곧 Γ⊨φ\Gamma \models \varphi이면 Γ⊢φ\Gamma \vdash \varphi이고, 이는 모든 집합 Γ\Gamma에 대해 성립하며, 이로부터 연역과 의미론적 귀결은 언제나 일치한다. 이 수업은 조합론적 응용으로 끝난다. 유한한 부분들의 채색으로부터 얻는 무한 그래프의 채색, 무한한 진술 속에 숨은 유한한 상한, 그리고 논리식의 집합이 표현할 수 있는 것의 한계이다.

학습 목표

  1. 유한 충족 가능한 집합을 정의하고, 변항의 값을 차례로 고정하는 방법으로 콤팩트성 정리를 증명하며, 불변량, 두 증인 논증, 일치 보조정리의 역할과 이 구성에 선택 공리가 필요하지 않은 이유를 설명한다.
  2. 콤팩트성의 동치인 형태들, 곧 충족 불가능성의 형태와 귀결의 형태를 진술하고, 증명하고, 적용하며, 각각에서 다른 형태로 옮겨 간다.
  3. 콤팩트성, 유한 전제 집합의 완전성, 단조성으로부터 강한 완전성을 이끌어 내고, 그로부터 연역과 의미론적 귀결의 일치, 그리고 무모순성과 충족 가능성의 일치를 얻는다.
  4. 무한 집합에 관한 조합론적 문제(채색, 순서, 짝짓기)를 논리식의 집합으로 부호화하고 콤팩트성으로 해결하며, 정리가 보장하는 것과 보장하지 않는 것을 구별한다.

앞의 수업들에서 쓰는 것

이 수업은 거의 전적으로 의미론 안에서 진행되며, 의미론에서 다음을 쓴다. 진리값 할당은 함수 v ⁣:V→{0,1}v\colon V \to \{0, 1\}이다. 그것은 집합 VV, 곧 변항 v1,v2,v3,…v_1, v_2, v_3, \ldots의 집합 위에 정의되며, 모든 논리식으로 유일한 방식으로 확장된다. 할당이 논리식의 집합 Γ\Gamma를 충족한다는 것(v⊨Γv \models \Gamma)은 그 각 논리식에 값 11을 준다는 것이고, Γ\Gamma는 어떤 할당이 그것을 충족하면 충족 가능, 그렇지 않으면 충족 불가능이다. 이 모든 것은 명제 논리의 의미론 수업에 있으며, 이 수업의 중심 도구인 일치 보조정리도 거기에 있다. 두 할당이 φ\varphi의 변항들(그것은 유한 집합 V(φ)V(\varphi)를 이룬다) 위에서 일치하면, 두 할당은 φ\varphi에 같은 값을 준다.

의미론적 귀결과 동치 수업에서는 Γ⊨φ\Gamma \models \varphi의 정의(Γ\Gamma를 충족하는 모든 할당은 φ\varphi도 충족한다), 그 구조적 성질들, 특히 단조성(Γ⊆Δ\Gamma \subseteq \Delta이고 Γ⊨φ\Gamma \models \varphi이면 Δ⊨φ\Delta \models \varphi이다)과 다섯째 성질(충족 불가능한 집합은 모든 논리식을 귀결로 가진다), 그리고 귀결과 충족 불가능성 정리를 쓴다. 곧 Γ⊨φ\Gamma \models \varphi인 것은 Γ∪{¬φ}\Gamma \cup \{\neg\varphi\}가 충족 불가능할 때 그리고 그때에만이다. 일반화된 드모르간 법칙과 분배 법칙 수업에서는 값 보조정리를 쓴다. ⋀i=1nφi\bigwedge_{i=1}^{n} \varphi_i의 값이 11인 것은 그 모든 항의 값이 11일 때 그리고 그때에만이고, ⋁i=1nφi\bigvee_{i=1}^{n} \varphi_i의 경우에는 어떤 항의 값이 11일 때 그리고 그때에만 그렇다. 마지막으로, ⊤:=(v1→v1)\top := (v_1 \rightarrow v_1)로 두면 이는 항진식이고, ⊥:=¬⊤\bot := \neg\top로 두면 이는 모순식이다.

연역 쪽에서는, 형식 연역 체계 수업이 단조성(Mon: Γ⊆Δ\Gamma \subseteq \Delta이고 Γ⊢φ\Gamma \vdash \varphi이면 Δ⊢φ\Delta \vdash \varphi이다)과 유한성(Fin: Γ⊢φ\Gamma \vdash \varphi이면, 어떤 유한 부분집합 Γ0\Gamma_0이 Γ\Gamma에 포함되면서 Γ0⊢φ\Gamma_0 \vdash \varphi를 만족한다)을 증명했고, 네 가지 연역 기법 수업은 둘 다 이 강좌의 체계(공리 도식 A1, A2, A3, 전건 긍정식, 이중 부정 대체(RDN))에서 성립함을 확인했다. 이하에서 기호 ⊢\vdash는 이 체계를 가리킨다. 끝으로, 건전성과 완전성 수업이 건전성 정리(Γ⊢φ\Gamma \vdash \varphi이면 Γ⊨φ\Gamma \models \varphi이며, 이는 모든 Γ\Gamma에 대해 성립한다)와 유한 전제 집합의 완전성을 증명했다. {γ1,…,γk}⊨φ\{\gamma_1, \ldots, \gamma_k\} \models \varphi이면 {γ1,…,γk}⊢φ\{\gamma_1, \ldots, \gamma_k\} \vdash \varphi이다.