FOL(7) - completeness and its equivalence

 

 we'll prove completeness theorem. but before that, we'll look at equivalence first.

 

completeness theorem(a) : $\Gamma \models \varphi \rightarrow \Gamma \vdash \varphi$.

 

completeness theorem(b) : if $\Gamma$ is consistent, then $\Gamma$ is satisfiable.

 

we'll prove (a) and (b) are equivalent and finally, on later posting, (b) will be considered.

 

 

$(a)\rightarrow (b)$. assume (a) holds but not (b). then $\Gamma$ is consistent and $\Gamma$ is unsatisfiable. that is, there does not exist $s$ and $\mathfrak{A}$ which satisfies all member of $\Gamma$ with $s$. thus vacuosly, we get $\Gamma \models \varphi$ and $\Gamma \models \neg\varphi$. then by (a), we get $\Gamma \vdash \varphi$ and $\Gamma \vdash \neg\varphi$ which is contradiction to consistency.

 

$(b)\rightarrow (a)$. suppose (b) holds and but (a) does not. then $\Gamma \models \varphi$ and $\Gamma \not\vdash \varphi$. then we get $\{\Gamma;\neg\varphi\}$ is unsatisfiable(*). using contraposition of (b), we get $\Gamma;\neg\varphi$ is inconsistent. thus $\Gamma;\neg\varphi \vdash \varphi$ and $\Gamma;\neg\varphi\vdash\neg\varphi$. thus we get $\Gamma \vdash \neg\varphi\rightarrow\neg\varphi$ and $\Gamma\vdash\neg\varphi\rightarrow\varphi$ using deduction theorem. then by rule T, we get $\Gamma\vdash\varphi$. which is contradiction.

 

* $\Gamma;\neg\varphi$ is unsatisfiable iff $\Gamma \models \varphi$.

$(\rightarrow)$. using definition of 'satisfiable' and satisfaction, $\Gamma;\neg\varphi \models \varphi$ and $\Gamma;\neg\varphi \models \neg\varphi$. then $\Gamma\models\neg\varphi\rightarrow\varphi$ and $\Gamma\models\neg\varphi\rightarrow\neg\varphi$. thus we get $\Gamma\models\varphi$

 

$(\leftarrow)$. $\Gamma\models\varphi$. then $\Gamma\models\varphi\rightarrow\varphi$. then $\Gamma\models\neg\varphi\rightarrow\neg\varphi$. then we get $\Gamma;\neg\varphi\models\neg\varphi$. and since $\Gamma\models\varphi$, trivially $\Gamma\models \neg\varphi\rightarrow\varphi$. thus $\Gamma;\neg\varphi\models\varphi$. then using definition of 'satisfaction(the meaning of $\models$)', we get $\Gamma;\neg\varphi$ is unsatisfiable.

 

since (a) and (b) are equivalent, it suffices to show that (b) can be proved.