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 well-known 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 non-empty (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 $𝔇:=\{S(\{A\})\mid A\in \mathrm{\Delta })$. Then every member of $𝔇$ is closed, and, by assumption and equation $(1)$, the intersection of any finite family of members of $𝔇$ is non-empty, which means that $\bigcap 𝔇\ne \mathrm{\varnothing }$. But $\bigcap 𝔇=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⊢⟂$, then $⊢B$, where $B$ is $A_1\to (A_2\to (\mathrm{\cdots }\to (A_n\to ⟂)\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 ⟂)\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 ⟂)\mathrm{\cdots })$ Then $v(A_1\to B)=1$ for all $v$. By the completeness theorem, $⊢A_1\to B$, and therefore $A_1,\mathrm{\dots },A_n⊢⟂$ 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 one-to-one 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	2013-03-22 19:35:21
Last modified on	2013-03-22 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