FOL(9) - compactness theorem and its equivalnce

 

compactness theorem(a) : if $\Gamma \models \varphi$, then there exists some finite $\Gamma_0 \subseteq \Gamma$ such that $\Gamma_0 \models \varphi$.

 

compactness theorem(b) : $\Gamma$ is finitely satisfiable iff $\Gamma$ is satisfiable.

(*definition : $\Gamma$ is finitely satisfiable iff every finite subset of $\Gamma$ is satisfiable)

 

(a) : suppose $\Gamma \models \varphi$. then $\Gamma\vdash\varphi$ by completeness. now consider deduction sequence $<a_1,\ldots,a_n>$ where $a_n=\varphi$ from $\Gamma$. define $\overline{\Gamma} =\{a_k|a_k \in \Gamma\}$(this is always possible since deduction is finite. and also by axiom of choice). trivially $\overline{\Gamma}$ is finite subset of $\Gamma$. thus we get $\overline{\Gamma}\vdash\varphi$(intuitively trivial. but if you want a proof, use induction for $a_i$ for all $i<k$ in deduction seqence). then by soundness, we get $\overline{\Gamma}\models\varphi$.

 

(b) same as in compactness for PL, it suffices to show that rightarrow condition. now suppose (b) is false. then $\Gamma$ is finitely satisfiable and $\Gamma$ is unsatisfiable. then by completeness theorem(b), we get $\Gamma$ is inconsistent. thus $\Gamma \vdash \varphi$ and $\Gamma\vdash\neg\varphi$. sames as (a), we get finite $\Gamma_0$ such that $\Gamma_0\vdash\varphi$ and $\Gamma_0\vdash\neg\varphi$. since $\Gamma_0$ is finite, it is satisfiable. thus consistent(by soundness(b)). now contradiction occurs.

 

 

now equivalence of (a) and (b) should be introduced.

 

$(a)\rightarrow (b)$. suppose (a) holds and (b) does not. then $\Gamma$ is finitely satisfiable but unsatisfiable. then we get $\Gamma\models\varphi$ and $\Gamma\models\neg\varphi$. then by (a), we get finite $\Gamma_0, \Gamma_1 \subseteq \Gamma$ such that $\Gamma_0\models\varphi$ and $\Gamma_1\models\neg\varphi$. define $\overline{\Gamma}=\Gamma_0 \cup \Gamma_1$. then we get $\overline{\Gamma}\models \varphi$ and $\overline{\Gamma}\models \neg\varphi$(*). since $\overline{\Gamma}$ is finite, by (b), $\overline{\Gamma}$ is satisfiable. thus we get $s$ and $\mathfrak{A}$ such that $\models_{\mathfrak{A}}\varphi[s]$ and $\models_{\mathfrak{A}}\neg\varphi[s]$. and latter part equals $\not\models_{\mathfrak{A}}\varphi[s]$. this yields contradiction.

 

*if $\Gamma \subseteq \Gamma^{*}$, then $\Gamma \models\varphi \rightarrow \Gamma^{*}\models\varphi$.

proof : suppose not. then $\Gamma^{*}\not\models\varphi$. then there exist some $s$ and $\mathfrak{A}$ such that $\Gamma^{*}$ with $s$ is satisfied but $\not\models_{\mathfrak{A}}\varphi[s]$. since $\Gamma^{*}$ is satisfied, its subset $\Gamma$ is satisfied. thus we get $\models_{\mathfrak{A}}\varphi[s]$ which is contradiction.

 

$(b)\rightarrow (a)$. same method in compactness theorem for PL is used. suppose (b) holds. use contraposition to (a). that is,

 

*useful fact : $\Gamma;\neg\varphi$ is unsatisfiable iff $\Gamma\models\varphi$

 

$\Gamma_0 \not\models \varphi$ for every finite $\Gamma_0 \subseteq \Gamma$

$\Rightarrow$ $\Gamma_0;\neg\varphi$ is satisfiable for every finite $\Gamma_0\subseteq\Gamma$

$\Rightarrow$ $\Gamma;\neg\varphi$ is finitely satisfiable

$\Rightarrow$ $\Gamma;\neg\varphi$ is satisfiable (by b)

$\Rightarrow$ $\Gamma\not\models\varphi$.

 

thus (a) and (b) are equivalent.

 

 

후... 드디어 끝났네요

여기까지가 기본적인 수리논리의 분야로 들어가기 위한 첫걸음마입니다. 앞으로는 기본적인 model theory와 computability theory의 개념들을 살펴보고, 괴델의 불완전성 정리(간략한 증명은 카테고리 '학문/미분류' 참조)를 증명할 것입니다. 괴델까지 끝난다면, 한국 학부 수준에서 배울 수 있는 수리논리학은 끝이라고 봐도 무방할 것 같습니다. 그 이후에는 별 계획은 없지만 양상논리(modal logic)을 살펴보거나, 연재된 글들을 전제해서 수리논리의 각 분야(model theory, set theory, proof theory, computability theory)를 탐구할 것입니다.

 

※이 글은 FOL(8) - completeness theorem 다음에 오는 글입니다. completeness는 복잡하여 아직 올라오지 않았기에 보다 쉬운 이 글이 먼저 올라왔습니다.