compactness theorem for PL(1)

we'll prove compactness theorem for propositional logic(PL). prerequisite is PL(1), PL(2) in my blog.

 

 

Definition 1 : A set $\Sigma$ of wffs is satisfiable if and only if there is a truth assignment that satisfies every member of $\Sigma$.

 

Definition 2 : A set $\Sigma$ of wffs is finitely satisfiable if and only if every finite subset of $\Sigma$ is satisfiable.

 

using above two definitions, we'll prove compactness theorem.

 

 

Compactness theorem : A set of wffs is satisfiable if and only if it is finitely satisfiable.

 

case 1 : finite set $\Sigma$ of wffs. for $(\rightarrow)$, since every member of $\Sigma$ is satisfied by truth assignment $v$, every member of any subset of $\Sigma$ is satisfied by $v$. this is trivial. for $(\leftarrow)$, since $\Sigma$ is a subset of itself, it is also clear.

 

case 2 : infinite set $\Sigma$ of wffs. about $(\rightarrow)$, it is same as case 1. you may prove these rigorously by using formal definition. but this is very easy so try freely. problem is when $(\leftarrow)$. we'll prove this.

 

 

$(\leftarrow)$. let a infinite set $\Sigma$ of wffs is finitely satisfiable. and let $\alpha_1, \alpha_2, \cdots$ be fixed wffs which are listed by any order. since the set of our symbols is finitie(thus countable) and every set of wffs is also countable, we can make a sequence for wffs like above;if you have a set theory knowledge, you can prove that.

 

now define $\Delta$ recursively.

 

$\Delta_0 = \Sigma$

$\Delta_{n+1}=\Delta_n;\alpha_{n+1} \quad \text{if this is finitely satisfiable}$
$\Delta_{n+1}=\Delta_n;(\neg \alpha_{n+1})  \quad\text{otherwise}$

where $\Delta_n;\alpha_{n+1}=\Delta_n \cup \{\alpha_{n+1}\}$.

 

notice that $\Delta_n$ is finitely satisfiable for all $n\in \mathbb{N}$. use reductio ad absurdum.

 

let $\Sigma$ be any set which is finitely satisfiable. assume $\Sigma;\alpha$ and $\Sigma;(\neg \alpha)$ are finitely unsatisfiable. then there exist some sets $\Sigma_1 ;\alpha$ and $\Sigma_2;(\neg \alpha)$ unsatisfiable where $\Sigma_1 \subseteq \Sigma$, and $\Sigma_2 \subseteq \Sigma$ are satisfiable.

 

define $\bar{\Sigma}=\Sigma_1 \cup \Sigma_2$. then $\bar{\Sigma} \subseteq \Sigma$ is finite thus satisfiable. but $\Sigma_1 ;\alpha$ is unsatisfiable, so there does not exist truth assignment $v$ which satisfies $\alpha$ for $\Sigma_1 ;\alpha$. that is, $\bar{v}(\alpha) \neq T$ for all truth assignment. thus it cannot be possible that there exist a truth assignment $v$ which satisfies $\alpha$ of $\bar{\Sigma};\alpha$. which means $\bar{v}(\alpha) \neq T$ for all $\bar{v}$. but also $\Sigma_2;(\neg \alpha)$ is unsatisfiable. thus $\bar{v}((\neg \alpha)) \neq T$ for all truth assignment for $\bar{\Sigma};\alpha$. since $\bar{v}(\alpha) \neq T$ and $\bar{v}((\neg \alpha)) \neq T$, contraction occurs with the definition of truth assignment. thus it cannot be possible $\Sigma;\alpha$ and $\Sigma;(\neg \alpha)$ are both unsatisfiable. this proves $\Delta_n$ is finitely satisfiable for all $n \in \mathbb{N}$.

 

Now let $\Delta = \cup_{n \in \mathbb{N}} \Delta_n$. then it is clear $\Sigma \subseteq \Delta$ and for any wff $\alpha$, $\alpha \in \Delta$ or $(\neg \alpha) \in \Delta$. and $\Delta$ itself is finitely satisfiable.

 

for the third property, observe $\Delta_1 \subseteq \Delta_2 \subseteq \cdots \subseteq \Delta_n \subseteq \cdots \subseteq \Delta$. and let $\bar{\Sigma}$ be any finite subset of $\Delta$. then $\bar{\Sigma} \subseteq \Delta = \cup_{n \in \mathbb{N}} \Delta_n \leftrightarrow \bar{\Sigma} \subseteq \Delta_i \text{for some i} \in \mathbb{N}$. and since $\Delta_i$ is finitely satisfiable, $\bar{\Sigma}$ is satisfiable. consequently, $\Delta$ is finitely satisfiable.

 

define truth assignemnt $v$ for the all sentence symbols as $v(A)=T$ if and only if $A \in \Delta$ for any sentence symbol. now claim that $v$ satisfies $\varphi$ if and only if $\varphi \in \Delta$. we'll use induction for $\varphi$.

 

(i) $\varphi=(\neg \alpha)$ where $\alpha$ is any wffs. give induction hypothesis $\bar{v}(\alpha)=T$ if and only if $\alpha \in \Delta$.

 

$(\rightarrow)$. let $\bar{v}(\varphi)=T$. then $\bar{v}(\alpha)=F$ which implies $\alpha \notin \Delta$. thus $(\neg \alpha) \in \Delta$ by second property of $\Delta$. thus $\varphi \in \Delta$. $(\leftarrow)$. let $\varphi \in \Delta$. then $\alpha \notin \Delta$. this implies $\bar{v}(\neg \alpha)=\bar{v}(\varphi)=T$.

 

(ii) $\varphi=(\alpha \wedge \beta)$ where $\alpha, \beta$ are any wffs. give induction hypothesis $\bar{v}(\alpha)=T$ if and only if $\alpha \in \Delta$ and $\bar{v}(\beta)=T$ if and only if $\beta \in \Delta$.

 

. check the last biconditional. $\{\alpha\} \cup \{\beta\} \subseteq \Delta$ is satisfiable. thus every truth assignment that satisfies $\alpha$and $\beta$ must satisfy $\alpha \wedge \beta$, and vice versa(formally, use reductio ad absurdum).

 

(iii) $\varphi=(\alpha \vee \beta)$ where $\alpha, \beta$ are any wffs. give inductive assumption that $\bar{v}(\alpha)=T$ if and only if $\alpha \in \Delta$ and $\bar{v}(\beta)=T$ if and only if $\beta \in \Delta$.

 

then $\bar{v}(\varphi)=T \leftrightarrow \bar{v}(\alpha)=T \vee \bar{v}(\beta)=T \leftrightarrow (\alpha \in \Delta) \vee (\beta \in \Delta) \leftrightarrow \alpha \vee \beta \in \Delta$.

 

for the last biconditional, suppose not. let $(\alpha \in \Delta) \vee (\beta \in \Delta)$ and $\alpha \vee \beta \notin \Delta$. then $\neg(\alpha \vee \beta) \in \Delta$. consider the finite set $\{\alpha, \neg(\alpha \vee \beta) \}$ and $\{\beta, \neg(\alpha \vee \beta)\}$. since they are subsets of $\Delta$, they must be satisfiable but cannot. you can check the other side conditional also.

 

(vi) $\varphi= (\alpha \rightarrow \beta)$ where $\alpha, \beta$ are any wffs. give inductive assumption that $\bar{v}(\alpha)=T$ if and only if $\alpha \in \Delta$ and $\bar{v}(\beta)=T$ if and only if $\beta \in \Delta$.

 

then $\bar{v}(\varphi)=T \leftrightarrow \bar{v}(\alpha)=F \vee \bar{v}(\beta)=T \leftrightarrow (\neg \alpha \in \Delta) \vee (\beta \in \Delta) \leftrightarrow (\alpha \rightarrow \beta) \in \Delta$. you can check last biconditional same as other case.

 

(v) $\varphi =(\alpha \leftrightarrow \beta)$where $\alpha, \beta$ are any wffs. same procedure is applied done in (i)-(iv).

 

now our claim is proved.

 

Since $\Sigma \subseteq \Delta$, every $\varphi \in \Sigma$ is satisfied by our truth assignment $v$. that is, $\bar{v}(\varphi)=T$ for all $\varphi \in \Sigma \subseteq \Delta$. thus compactness theorem is proved.