completeness theorem for PL

 

 

completeness theorem : $\Sigma \models \tau \rightarrow \Sigma \vdash \tau$.

 

Proof

 

let $\Sigma \models \tau$. then by compactness theorem^[각주:1], we get some finite set $\Sigma_0 \subseteq \Sigma$ such that $\Sigma_0 \models \tau$. let $\Sigma_0 =\{a_0, a_1, \ldots, a_n\}$. then $\{a_0, a_1, \ldots, a_n\} \models \tau$. then we get $\models a_0 \rightarrow a_1 \rightarrow a_2 \ldots \rightarrow a_n \rightarrow \tau$. for this, you must check $\Sigma;\alpha \models \beta \leftrightarrow \Sigma \models (\alpha \rightarrow \beta)$. i'll leave out this for readers.

 

consider deduction sequence $<b_0,b_1,\ldots,b_i>$ends with $\tau$ from $\Sigma$.

 

for $\models a_0 \rightarrow a_1 \rightarrow a_2 \ldots \rightarrow a_n \rightarrow \tau$, choose $b_0=a_0 \rightarrow a_1 \rightarrow a_2 \ldots \rightarrow a_n \rightarrow \tau$ which is tautology. then $b_1=a_0$, and by modus ponens, we get $b_2=a_1 \rightarrow a_2 \ldots \rightarrow a_n \rightarrow \tau$. by using modus ponens finitely, we get $a_k=\tau$ for some $k$ finite. this means there exist some deduction ends with $\tau$ from $\Sigma$. now we get $\Sigma \vdash \tau$. hence, completeness theorem is proved.

 

 

1. refer to compactness theorem(1), (2), (3). actually, compactness theorem and its corollary are often named same as compactness theorem. in this case, I refer readers corollary. [본문으로]