# compactness theorem for classical propositional logic

###### Theorem 1.

(Compactness Theorem) $\Delta$ is sound iff every finite subset of it is sound.

Proof using Konig’s lemma. Let $A_{1},\ldots$ be an enumeration of all the wff’s in $\Delta$ (this assumes that the set $V$ of all propositional variables is countable). Let $i_{1}\leq\ldots$ be positive integers such that $p_{1},\ldots,p_{i_{n}}$ are the propositional variables that occur in wff’s $A_{1},\ldots,A_{n}$. Since $\{A_{1},\ldots,A_{n}\}$ is sound, the set $S_{n}:=\{v\in 2^{V}\mid v(A_{j})=1,j=1,\ldots,n\}\neq\varnothing$ for each $n$. Furthermore, $S_{n+1}\subseteq S_{n}$. Let $U_{n}:=\{v(p_{1})\cdots v(p_{n})\mid v\in S_{n}\}$. In other words, each $U_{n}$ is a set of words over $\{0,1\}$ of length $n$. Then $U_{n}$ is finite and non-empty (because $S_{n}\neq\varnothing$) for each $n$. Since $\varnothing\neq S_{n+1}\subseteq S_{n}$, there is a word in $U_{n}$ that is a prefix of a word in $U_{n+1}$ for each $n$.

Let $T$ be the tree with root $r$ (some arbitrary symbol) such that

1. 1.

its vertices other than $r$ are elements of $U_{1},\ldots,U_{n},\ldots$.

2. 2.

the children of $r$ are elements of $U_{1}$,

3. 3.

if $\ell\in U_{n}$ is a vertex, then its children are elements of $U_{n+1}$ with prefix $\ell$

It’s easy to see that $T$ is finitely branching, since each $U_{n}$ is finite. Furthermore, by induction  , if $\ell\in U_{n+1}$, then its prefix of length $n$, an element of $U_{n}$, is a vertex $\ell^{\prime}$ of $T$. So $\ell$, as a child of $\ell^{\prime}$, is a vertex $T$. Since each $U_{n}\neq\varnothing$ for each $n$, the $T$ has infinitely many vertices. As a result, we apply Konig’s lemma, so that $T$ has an infinite branch $T^{\prime}$. It is easy to see that $T^{\prime}$ corresponds to an infinite word $\alpha$ over $\{0,1\}$, which in turn corresponds to an interpretation $v$ such that $v(p_{i})$ is the $i$’th letter in $\alpha$. It is now clear that $v(A_{i})=1$ for each $A_{i}\in\Delta$, hence $\Delta$ is sound. $\square$

Proof using Tychonoff’s theorem. For any set $\Delta$ of wff’s, define $S(\Delta):=\{v\in 2^{V}\mid v(A)=1,\mbox{ for all }A\in\Delta\}$. It is easy to see that

 $S(\bigcup\{\Delta_{i}\mid i\in I\})=\bigcap\{S(\Delta_{i})\mid i\in I\}$ (1)

for $v$ is in the former set iff $v(A)=1$ for all $A\in\bigcup\{\Delta_{i}\mid i\in I\}$ iff $v(A_{i})=1$ for all $A_{i}\in\Delta_{i}$, $i\in I$, iff $v$ in the later set.

Next, equip $2:=\{0,1\}$ with the discrete topology, and $2^{V}$ the product topology. Since $2$ is compact  , so is $2^{V}$ by the Tychonoff’s theorem, and therefore the finite intersection property applies. In addition, for any wff $A$, $S(\{A\})$ is closed in $2^{V}$, since there are only a finite number of propositional variables occurring in $A$. As a result, by equation $(1)$, $S(\Delta)$ is closed for any set $\Delta$ of wff’s.

Now, suppose every finite subset of $\Delta$ is sound. In particular, every singleton subset of $\Delta$ is sound. This means that for each $A\in\Delta$, $S(\{A\})\neq\varnothing$. Let $\mathfrak{D}:=\{S(\{A\})\mid A\in\Delta)$. Then every member of $\mathfrak{D}$ is closed, and, by assumption  and equation $(1)$, the intersection  of any finite family of members of $\mathfrak{D}$ is non-empty, which means that $\bigcap\mathfrak{D}\neq\varnothing$. But $\bigcap\mathfrak{D}=S(\Delta)$ by equation $(1)$, the result follows. $\square$

By the compactness theorem, one can show that soundness and consistency are the semantical and syntactical sides of the same idea.

###### Proof.

If $A_{1},\ldots,A_{n}\vdash\perp$, then $\vdash B$, where $B$ is $A_{1}\to(A_{2}\to(\cdots\to(A_{n}\to\perp)\cdots)$, or $v(B)=1$ for all $v$, or $v(A_{1})=0$ or $v(A_{2}\to(\cdots\to(A_{n}\to\perp)\cdots))=1$, or $v(A_{1})=0$ or $v(A_{2})=0$ or $\cdots$ or $v(A_{n})=0$ for all $v$, by induction, or $v(A_{i})=0$ for some $i$, where $i=1,\ldots,n$, which means $\{A_{1},\ldots,A_{n}\}$ is not sound.

Conversely, if $\{A_{1},\ldots,A_{n}\}$ is not sound, then $v(A_{i})=0$ for some $i$, where $i=1,\ldots,n$ for all $v$. Renumber if necessary, so that the indices $1$ and $i$ are switched, and $v(A_{1})=0$ for all $v$. Let $B$ be the formula   $A_{2}\to(\cdots\to(A_{n}\to\perp)\cdots)$ Then $v(A_{1}\to B)=1$ for all $v$. By the completeness theorem, $\vdash A_{1}\to B$, and therefore $A_{1},\ldots,A_{n}\vdash\perp$ by the deduction theorem  $n$ times. ∎

###### Proposition 1.

Soundness and consistency are the same on all sets.

###### Proof.

For one direction, see here (http://planetmath.org/PropertiesOfConsistency). Now, suppose $\Delta$ is consistent. Then every finite subset of it is consistent, and therefore sound by the last proposition, hence $\Delta$ itself is sound by the compactness theorem. ∎

A set $\Delta$ of wff’s is uniquely sound if there is a unique interpretation $v$ such that $v(A)=1$ for every $A\in\Delta$.

###### Corollary 1.

A set is maximally consistent iff it is a uniquely sound theory.

###### Proof.

If $\Delta$ is maximally consistent, then it is a theory (see here (http://planetmath.org/MaximallyConsistent)), and sound by the last corollary. Suppose $v_{1}(A)=v_{2}(A)=1$ for all $A\in\Delta$. If $v_{1}\neq v_{2}$, then there is some wff $B\notin\Delta$ such that $v_{1}(B)\neq v_{2}(B)$. So one of them is $1$, say $v_{1}(B)=1$. Then $\Delta\cup\{B\}$ is sound, and therefore consistent by the last corollary, contradicting the maximality of $\Delta$.

We actually proved more: any maximally consistent $\Delta$ is $\{A\mid v(A)=1\}$, where $v$ is the unique interpretation such that $v(A)=1$ for all $A\in\Delta$. One direction is obvious. The other direction comes from the fact that $\{A\mid v(A)=1\}$ is consistent and $\Delta$ is maximal.

Conversely, suppose a theory $\Delta$ is uniquely sound. Then $\Delta=\mbox{Ded}(\Delta)=\bigcap\{\Gamma\in W_{L}\mid\Delta\subseteq\Gamma\}$, where $W_{L}$ is the set of all maximally consistent sets of the logic $L$. Suppose $\{\Gamma\in W_{L}\mid\Delta\subseteq\Gamma\}$ has at least two elements, say, $\Gamma_{1},\Gamma_{2}$. Then by the last paragraph, they are both uniquely sound. Let $v_{1},v_{2}$ be the two respective unique interpretations such that $v_{i}(A)=1$ for every $A\in\Gamma_{i}$, $i=1,2$. Since $\Gamma_{1}\neq\Gamma_{2}$, there is a wff $B\in\Gamma_{1}-\Gamma_{2}$ such that $v_{1}(B)=1$ and $v_{2}(B)=0$. In addition, $v_{1}(A)=v_{2}(A)=1$ for all $A\in\Delta$, which forces $v_{1}=v_{2}$ because $\Delta$ is uniquely sound. But this contradicts the inequality $v_{2}(B)\neq v_{2}(B)$. Therefore, $\{\Gamma\in W_{L}\mid\Delta\subseteq\Gamma\}$ has exactly one element, which is $\Delta$. ∎

Remark. It is easy to see that $\Delta_{v}:=\{A\mid v(A)=1\}$ is maximally consistent for any interpretation $v$: it is sound, and therefore consistent; it is maximal, for given any wff $B$, either $v(B)=1$ or $v(B)=0$, so that either $B\in\Delta_{v}$ or $\neg B\in\Delta_{v}$. Coupled with the corollary above, there is a one-to-one correspondence $v\mapsto\Delta_{v}$ between interpretations and maximally consistent sets of a logic.

Title compactness theorem for classical propositional logic CompactnessTheoremForClassicalPropositionalLogic 2013-03-22 19:35:21 2013-03-22 19:35:21 CWoo (3771) CWoo (3771) 14 CWoo (3771) Theorem msc 03B05 sound uniquely sound