compactness theorem for classical propositional logic
Call a set $\mathrm{\Delta}$ of wff’s of (classical) propositional logic^{} sound if there is an interpretation^{} (or valuation) $v$ such that $v(A)=1$ for every $A\in \mathrm{\Delta}$.
Theorem 1.
(Compactness Theorem) $\mathrm{\Delta}$ is sound iff every finite subset of it is sound.
One direction is trivial. The converse^{} is trivial too if $\mathrm{\Delta}$ is finite. We now prove that if every finite subset of an infinite set^{} $\mathrm{\Delta}$ is sound, so is $\mathrm{\Delta}$. There are two wellknown proofs of this, one assumes that the set $V$ of propositional variables is countable^{}, and the other does not. The one that does uses Konig’s lemma, and the other one uses Tychonoff^{}’s theorem (hence the name compactness theorem).
Proof using Konig’s lemma. Let ${A}_{1},\mathrm{\dots}$ be an enumeration of all the wff’s in $\mathrm{\Delta}$ (this assumes that the set $V$ of all propositional variables is countable). Let ${i}_{1}\le \mathrm{\dots}$ be positive integers such that ${p}_{1},\mathrm{\dots},{p}_{{i}_{n}}$ are the propositional variables that occur in wff’s ${A}_{1},\mathrm{\dots},{A}_{n}$. Since $\{{A}_{1},\mathrm{\dots},{A}_{n}\}$ is sound, the set ${S}_{n}:=\{v\in {2}^{V}\mid v({A}_{j})=1,j=1,\mathrm{\dots},n\}\ne \mathrm{\varnothing}$ for each $n$. Furthermore, ${S}_{n+1}\subseteq {S}_{n}$. Let ${U}_{n}:=\{v({p}_{1})\mathrm{\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 nonempty (because ${S}_{n}\ne \mathrm{\varnothing}$) for each $n$. Since $\mathrm{\varnothing}\ne {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.
its vertices other than $r$ are elements of ${U}_{1},\mathrm{\dots},{U}_{n},\mathrm{\dots}$.

2.
the children of $r$ are elements of ${U}_{1}$,

3.
if $\mathrm{\ell}\in {U}_{n}$ is a vertex, then its children are elements of ${U}_{n+1}$ with prefix $\mathrm{\ell}$
It’s easy to see that $T$ is finitely branching, since each ${U}_{n}$ is finite. Furthermore, by induction^{}, if $\mathrm{\ell}\in {U}_{n+1}$, then its prefix of length $n$, an element of ${U}_{n}$, is a vertex ${\mathrm{\ell}}^{\prime}$ of $T$. So $\mathrm{\ell}$, as a child of ${\mathrm{\ell}}^{\prime}$, is a vertex $T$. Since each ${U}_{n}\ne \mathrm{\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 \mathrm{\Delta}$, hence $\mathrm{\Delta}$ is sound. $\mathrm{\square}$
Proof using Tychonoff’s theorem. For any set $\mathrm{\Delta}$ of wff’s, define $S(\mathrm{\Delta}):=\{v\in {2}^{V}\mid v(A)=1,\text{for all}A\in \mathrm{\Delta}\}$. It is easy to see that
$$S(\bigcup \{{\mathrm{\Delta}}_{i}\mid i\in I\})=\bigcap \{S({\mathrm{\Delta}}_{i})\mid i\in I\}$$  (1) 
for $v$ is in the former set iff $v(A)=1$ for all $A\in \bigcup \{{\mathrm{\Delta}}_{i}\mid i\in I\}$ iff $v({A}_{i})=1$ for all ${A}_{i}\in {\mathrm{\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(\mathrm{\Delta})$ is closed for any set $\mathrm{\Delta}$ of wff’s.
Now, suppose every finite subset of $\mathrm{\Delta}$ is sound. In particular, every singleton subset of $\mathrm{\Delta}$ is sound. This means that for each $A\in \mathrm{\Delta}$, $S(\{A\})\ne \mathrm{\varnothing}$. Let $\U0001d507:=\{S(\{A\})\mid A\in \mathrm{\Delta})$. Then every member of $\U0001d507$ is closed, and, by assumption^{} and equation $(1)$, the intersection^{} of any finite family of members of $\U0001d507$ is nonempty, which means that $\bigcap \U0001d507\ne \mathrm{\varnothing}$. But $\bigcap \U0001d507=S(\mathrm{\Delta})$ by equation $(1)$, the result follows. $\mathrm{\square}$
Remark. It can be shown that the general version of the compactness theorem is equivalent^{} to the prime ideal theorem in Boolean algebra^{}.
By the compactness theorem, one can show that soundness and consistency are the semantical and syntactical sides of the same idea.
Lemma 1.
Soundness and consistency are the same on finite sets^{}.
Proof.
If ${A}_{1},\mathrm{\dots},{A}_{n}\u22a2\u27c2$, then $\u22a2B$, where $B$ is ${A}_{1}\to ({A}_{2}\to (\mathrm{\cdots}\to ({A}_{n}\to \u27c2)\mathrm{\cdots})$, or $v(B)=1$ for all $v$, or $v({A}_{1})=0$ or $v({A}_{2}\to (\mathrm{\cdots}\to ({A}_{n}\to \u27c2)\mathrm{\cdots}))=1$, or $v({A}_{1})=0$ or $v({A}_{2})=0$ or $\mathrm{\cdots}$ or $v({A}_{n})=0$ for all $v$, by induction, or $v({A}_{i})=0$ for some $i$, where $i=1,\mathrm{\dots},n$, which means $\{{A}_{1},\mathrm{\dots},{A}_{n}\}$ is not sound.
Conversely, if $\{{A}_{1},\mathrm{\dots},{A}_{n}\}$ is not sound, then $v({A}_{i})=0$ for some $i$, where $i=1,\mathrm{\dots},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 (\mathrm{\cdots}\to ({A}_{n}\to \u27c2)\mathrm{\cdots})$ Then $v({A}_{1}\to B)=1$ for all $v$. By the completeness theorem, $\u22a2{A}_{1}\to B$, and therefore ${A}_{1},\mathrm{\dots},{A}_{n}\u22a2\u27c2$ 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 $\mathrm{\Delta}$ is consistent. Then every finite subset of it is consistent, and therefore sound by the last proposition, hence $\mathrm{\Delta}$ itself is sound by the compactness theorem. ∎
A set $\mathrm{\Delta}$ of wff’s is uniquely sound if there is a unique interpretation $v$ such that $v(A)=1$ for every $A\in \mathrm{\Delta}$.
Corollary 1.
A set is maximally consistent iff it is a uniquely sound theory.
Proof.
If $\mathrm{\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 \mathrm{\Delta}$. If ${v}_{1}\ne {v}_{2}$, then there is some wff $B\notin \mathrm{\Delta}$ such that ${v}_{1}(B)\ne {v}_{2}(B)$. So one of them is $1$, say ${v}_{1}(B)=1$. Then $\mathrm{\Delta}\cup \{B\}$ is sound, and therefore consistent by the last corollary, contradicting the maximality of $\mathrm{\Delta}$.
We actually proved more: any maximally consistent $\mathrm{\Delta}$ is $\{A\mid v(A)=1\}$, where $v$ is the unique interpretation such that $v(A)=1$ for all $A\in \mathrm{\Delta}$. One direction is obvious. The other direction comes from the fact that $\{A\mid v(A)=1\}$ is consistent and $\mathrm{\Delta}$ is maximal.
Conversely, suppose a theory $\mathrm{\Delta}$ is uniquely sound. Then $\mathrm{\Delta}=\text{Ded}(\mathrm{\Delta})=\bigcap \{\mathrm{\Gamma}\in {W}_{L}\mid \mathrm{\Delta}\subseteq \mathrm{\Gamma}\}$, where ${W}_{L}$ is the set of all maximally consistent sets of the logic $L$. Suppose $\{\mathrm{\Gamma}\in {W}_{L}\mid \mathrm{\Delta}\subseteq \mathrm{\Gamma}\}$ has at least two elements, say, ${\mathrm{\Gamma}}_{1},{\mathrm{\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 {\mathrm{\Gamma}}_{i}$, $i=1,2$. Since ${\mathrm{\Gamma}}_{1}\ne {\mathrm{\Gamma}}_{2}$, there is a wff $B\in {\mathrm{\Gamma}}_{1}{\mathrm{\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 \mathrm{\Delta}$, which forces ${v}_{1}={v}_{2}$ because $\mathrm{\Delta}$ is uniquely sound. But this contradicts the inequality ${v}_{2}(B)\ne {v}_{2}(B)$. Therefore, $\{\mathrm{\Gamma}\in {W}_{L}\mid \mathrm{\Delta}\subseteq \mathrm{\Gamma}\}$ has exactly one element, which is $\mathrm{\Delta}$. ∎
Remark. It is easy to see that ${\mathrm{\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 {\mathrm{\Delta}}_{v}$ or $\mathrm{\neg}B\in {\mathrm{\Delta}}_{v}$. Coupled with the corollary above, there is a onetoone correspondence $v\mapsto {\mathrm{\Delta}}_{v}$ between interpretations and maximally consistent sets of a logic.
Title  compactness theorem for classical propositional logic 

Canonical name  CompactnessTheoremForClassicalPropositionalLogic 
Date of creation  20130322 19:35:21 
Last modified on  20130322 19:35:21 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  14 
Author  CWoo (3771) 
Entry type  Theorem 
Classification  msc 03B05 
Defines  sound 
Defines  uniquely sound 
\@unrecurse 