Compactness for Classical Propositional Logic

Compactness

Let a consequence relation $⊢$ for some logic $L$ be given. $⊢$ is compact if, and only if:

$$\Gamma ⊢x⟹\exists {\Gamma }_{fin}\subseteq \Gamma \text{ such that }{\Gamma }_{fin}⊢x$$

where ${\Gamma }_{fin}$ is a finite subset of $\Gamma$.

In this note, we are interested in compactness for classical propositional logic. We will treat $⊢$ semantically.

Classical Propositional Logic and Semantic Consequence ( $⊢$)

Let $\mathcal{L}$ be our standard propositional language, $\mathbb{V}$ be the set of all possible valuations (worlds) $v:\Phi \to \{0,1\}$, and $\models$ the usual satisfaction relation on $\mathbb{V}\times \mathcal{L}$.

We define classical consequence $⊢$ as follows: $\Gamma ⊢\varphi ⟺\text{For all }v\in \mathbb{V}:\text{if }v\models \gamma \text{ for all }\gamma \in \Gamma \text{, then }v\models \varphi$

(Note: Many logic textbooks use $\models$ for semantic consequence as well as for the satisfaction relation $\models \subseteq \mathbb{V}\times \mathcal{L}$.)

Because of how this consequence relation is constructed, we can prove that $⊢$ has several crucial structural properties:

Structural Properties of $⊢$

Let $⊢$ be classical semantic consequence. $⊢$ satisfies the following properties:

1. Reflexivity: If $\varphi \in \Gamma$, then $\Gamma ⊢\varphi$.
2. Monotonicity: If $\Gamma ⊢\varphi$ and $\Gamma \subseteq \Delta$, then $\Delta ⊢\varphi$.
3. Transitivity: If $\Gamma ⊢\psi$ for all $\psi \in \Delta$, and $\Delta ⊢\varphi$, then $\Gamma ⊢\varphi$.
4. Disjunction of Premises (Proof by Cases): If $\Gamma \cup \{\varphi \}⊢\chi$ and $\Gamma \cup \{\psi \}⊢\chi$, then $\Gamma \cup \{\varphi \vee \psi \}⊢\chi$.

---

We can show that Compactness holds for classical logic. We can give two proofs for it. To prove ^442bae using the first method, we need the following concepts:

Well-Behaved Set of Formulas

Consider $F\subseteq \mathcal{L}$, where $\mathcal{L}$ is the set of well-formed formulas consisting only of $\wedge ,\vee ,\neg$. The set $F$ is well-behaved iff, for all formulas $a,b\in \mathcal{L}$:

1. $a\wedge b\in F⟺a\in F\text{ and }b\in F$,
2. $a\vee b\in F⟺a\in F\text{ or }b\in F$,
3. $\neg a\in F⟺a\notin F$.

Lemma

1. For any valuation function $v:\mathcal{L}\to \{0,1\}$, the set $\{a\in \mathcal{L}:v(a)=1\}$ is well-behaved.
2. For all $F\subseteq \mathcal{L}$, if $F$ is well-behaved, then there exists a valuation function $v$ such that $F=\{a\in \mathcal{L}:v(a)=1\}$.

bproof

(1) Consider an arbitrary valuation function $v:\mathcal{L}\to \{1,0\}$ and the set $V=\{a\in \mathcal{L}:v(a)=1\}$. Consider arbitrary formulas $a,b\in \mathcal{L}$.

1. $\neg a\in V⟺v(\neg a)=1⟺v(a)=0⟺a\notin V$.
2. $a\wedge b\in V⟺v(a\wedge b)=1⟺v(a)=1\text{ and }v(b)=1⟺a\in V\text{ and }b\in V$.
3. $a\vee b\in V⟺v(a\vee b)=1⟺v(a)=1\text{ or }v(b)=1⟺a\in V\text{ or }b\in V$.

So, $V=\{a\in \mathcal{L}:v(a)=1\}$ is well-behaved.

(2) Consider an arbitrary well-behaved $F\subseteq \mathcal{L}$. Let us define $v_F:\mathcal{L}\to \{1,0\}$ as

$$v_F(a)=\{\begin{array}{ll}1& a\in F\\ 0& a\notin F\end{array}$$

and let us show it is a valuation function.

1. First, $v_F$ is a function. Take any $a\in \mathcal{L}$. Either $a\in F$ or $a\notin F$. If $a\in F$, $v_F(a)=1$, and if $a\notin F$, $v_F(a)=0$. Either way, $v_F$ assigns a unique value (0 or 1) to $a$, for any $a\in \mathcal{L}$. So $v_F$ is a function.
2. Second, let us show that $v_F$ is an assignment. This immediately follows from the step above, for the set of propositional variables $\Phi \subseteq \mathcal{L}$ and $v_F$ is already defined on the entirety of $\mathcal{L}$.
3. Third, let us show that $v_F$ is a valuation. It means that the values for complex formulas are assigned according to the usual rules. Consider arbitrary $a,b\in \mathcal{L}$:
   1. $v_F(\neg a)=1⟺\neg a\in F⟺a\notin F⟺v_F(a)=0$.
   2. $v_F(a\wedge b)=1⟺a\wedge b\in F⟺a\in F\text{ and }b\in F⟺v_F(a)=1\text{ and }{v}_F(b)=1$.
   3. $v_F(a\vee b)=1⟺a\vee b\in F⟺a\in F\text{ or }b\in F⟺v_F(a)=1\text{ or }{v}_F(b)=1$.

Therefore $v_F$ is indeed a valuation function. eproof

Compactness for Classical Logic

The classical consequence relation $⊢$ (or equivalently the operation $Cn$) is compact.

bproof Let us prove the theorem contrapositively. Let $\Gamma \subseteq \mathcal{L}$ and suppose that, for all finite ${\Gamma }_{fin}\subseteq \Gamma$, ${\Gamma }_{fin}⊬x$. Let us prove that $\Gamma ⊬x$. We will construct a chain of sets ${\Gamma }_i$ resulting in a set ${\Gamma }^{+}$ such that $\Gamma \subseteq {\Gamma }^{+}$, and show that this is the maximal subset of $\mathcal{L}$ such that no finite subset implies $x$. Then, we will prove that this set is well-behaved, which implies that $\neg x\in {\Gamma }^{+}$, and by ^bc81d0 that there exists a valuation $v$ such that $v({\Gamma }^{+})=1$. We will conclude that since $v({\Gamma }^{+})=1$ and $v(x)=0$, $\Gamma ⊬x$.

First, note that the set $\mathcal{L}$ is countable, for there is an injective function $\mathrm{G}:\mathcal{L}\to \mathbb{N}$ such that $G(a)$ is the Gödel number of $a$. So, we can list all the members of $\mathcal{L}$ as $a_1,a_2,a_3,\dots$. Second, define the following property:

$$P(\Delta ):⟺\text{For all finite }S\subseteq \Delta \text{: }S⊬x$$

Let us define the following chain of sets:

$$\begin{array}{rlrl}1.& & {\Gamma }_0& :=\Gamma \\ 2.& & {\Gamma }_{n+1}& :=\{\begin{array}{ll}{\Gamma }_n\cup \{a_n\}& \text{if }P({\Gamma }_n\cup \{a_n\})\\ {\Gamma }_n& \text{otherwise}\end{array}\end{array}$$

Then, define

$${\Gamma }^{+}:=\bigcup _{i=0}^{\infty }{\Gamma }_i$$

Let us now establish two key properties of ${\Gamma }^{+}$.

1. ($\Gamma \subseteq {\Gamma }^{+}$) First, $\Gamma \subseteq {\Gamma }^{+}$ obviously holds, for $\Gamma ={\Gamma }_0\subseteq {\Gamma }^{+}$.
2. ($P({\Gamma }^{+})$ holds) Second, $P({\Gamma }^{+})$ holds. Let us first prove by induction that $P({\Gamma }_i)$ holds for all $i\ge 0$. First, we have $P({\Gamma }_0)$ ex hypothesi. Suppose now that $P({\Gamma }_n)$ holds (IH), and let us show that $P({\Gamma }_{n+1})$ holds. Consider the set ${\Gamma }_n\cup \{a_n\}$. We have two cases. If $P({\Gamma }_n\cup \{a_n\})$ does not hold, then ${\Gamma }_{n+1}={\Gamma }_n$, and by the IH $P({\Gamma }_{n+1})$ holds. If $P({\Gamma }_n\cup \{a_n\})$ holds, ${\Gamma }_{n+1}={\Gamma }_n\cup \{a_n\}$, from which it immediately follows that $P({\Gamma }_{n+1})$ holds. Therefore, $P({\Gamma }_i)$ holds for all $i\ge 0$. Suppose now for reductio that $P({\Gamma }^{+})$ does not hold. It follows that there exists a finite $S\subseteq {\Gamma }^{+}$ such that $S⊢x$. Since ${\Gamma }^{+}$ is the union of a chain of sets $\Gamma \subseteq {\Gamma }_1\subseteq {\Gamma }_2\subseteq \dots$ and $S$ is finite, there must be some ${\Gamma }_j$ such that $S\subseteq {\Gamma }_j$. Since $S$ is finite, $S⊢x$, and $S\subseteq {\Gamma }_j$, we have that $P({\Gamma }_j)$ does not hold. However, this contradicts the fact that $P({\Gamma }_i)$ holds for all $i\ge 0$. Therefore, $P({\Gamma }^{+})$ must hold.
3. (${\Gamma }^{+}$ is a maximal $P$-set) Let us prove that ${\Gamma }^{+}$ is the maximal subset of $\mathcal{L}$ satisfying $P$. Suppose that there exists a set ${\Gamma }^{++}$ such that ${\Gamma }^{+}\subset {\Gamma }^{++}$. We will show that $P({\Gamma }^{++})$ fails. Since the inclusion is strict, there exists some $y\in {\Gamma }^{++}$ such that $y\notin {\Gamma }^{+}$. In our enumeration, $y=a_n$ for some $n$. Since $a_n\notin {\Gamma }^{+}$, it implies $a_n\notin {\Gamma }_{n+1}\subseteq {\Gamma }^{+}$. By the definition of our chain, $a_n$ is excluded only if $P({\Gamma }_n\cup \{a_n\})$ is false. This means there is a finite set $S\subseteq {\Gamma }_n\cup \{y\}$ such that $S⊢x$. Now, observe that ${\Gamma }_n\subseteq {\Gamma }^{+}\subset {\Gamma }^{++}$ and $y\in {\Gamma }^{++}$. So ${\Gamma }_n\cup \{y\}\subseteq {\Gamma }^{++}$, and hence, $S\subseteq {\Gamma }^{++}$. Since ${\Gamma }^{++}$ contains a finite subset $S$ that entails $x$, $P({\Gamma }^{++})$ fails. Thus, no proper superset of ${\Gamma }^{+}$ satisfies $P$.

Let us now show that ${\Gamma }^{+}$ is well-behaved.

1. (Negation: $\neg a\in {\Gamma }^{+}⟺a\notin {\Gamma }^{+}$ ) ($⟹$) Suppose $\neg a\in {\Gamma }^{+}$. If $a\in {\Gamma }^{+}$, it follows that $\{a,\neg a\}\subseteq {\Gamma }^{+}$, and since (i) $\{a,\neg a\}⊢x$ (a contradiction semantically entails everything) and (ii) $\{a,\neg a\}$ is finite, $P({\Gamma }^{+})$ does not hold, contradicting (2) above. Hence $a\notin {\Gamma }^{+}$. ($⟸$) Suppose $a\notin {\Gamma }^{+}$. Since ${\Gamma }^{+}$ is the maximal $P$-set, $P({\Gamma }^{+}\cup \{a\})$ does not hold, meaning that there exists some finite $S_1\subseteq {\Gamma }^{+}\cup \{a\}$ such that $S_1⊢x$. Suppose for reductio that $\neg a\notin {\Gamma }^{+}$. By the maximality of ${\Gamma }^{+}$, we have that $P({\Gamma }^{+}\cup \{\neg a\})$ does not hold, meaning that there exists some finite $S_2\subseteq {\Gamma }^{+}\cup \{\neg a\}$ such that $S_2⊢x$. Let $S:=(S_1\setminus \{a\})\cup (S_2\setminus \{\neg a\})$. Note, $S\subseteq {\Gamma }^{+}$ and $S$ is finite. Note that $S\cup \{a\}=S_1\cup (S_2\setminus \{\neg a\})$, and since $S_1⊢x$ and $⊢$ is monotonic, $S\cup \{a\}⊢x$. Analogously, $S\cup \{\neg a\}=(S_1\setminus \{a\})\cup S_2$, and since $S_2⊢x$, $S\cup \{\neg a\}⊢x$. By the Property of Disjunction of Premises – see ^2970ed – we get $S\cup \{a\vee \neg a\}⊢x$. Since $a\vee \neg a$ is a tautology, any valuation that satisfies $S$ will trivially satisfy $S\cup \{a\vee \neg a\}$, and thus will satisfy $x$. Therefore, $S⊢x$, contradicting $P({\Gamma }^{+})$. Therefore, $\neg a\in {\Gamma }^{+}$.
2. (Conjunction: $a\wedge b\in {\Gamma }^{+}⟺a,b\in {\Gamma }^{+}$) ($⟹$) Suppose $a\wedge b\in {\Gamma }^{+}$. If $a\notin {\Gamma }^{+}$, by the step above $\neg a\in {\Gamma }^{+}$, and hence $\{a\wedge b,\neg a\}\subseteq {\Gamma }^{+}$. Since $\{a\wedge b,\neg a\}⊢x$ and is finite, $P({\Gamma }^{+})$ does not hold: contradiction. The argument for $b$ is analogous. So, both $a,b$ must be in ${\Gamma }^{+}$. ($⟸$) Suppose $a,b\in {\Gamma }^{+}$. If $a\wedge b\notin {\Gamma }^{+}$, then $\neg (a\wedge b)\in {\Gamma }^{+}$. Since $\{a,b,\neg (a\wedge b)\}⊢x$ and is a finite subset of ${\Gamma }^{+}$, $P({\Gamma }^{+})$ does not hold: contradiction. So, $a\wedge b\in {\Gamma }^{+}$.
3. (Disjunction: $a\vee b\in {\Gamma }^{+}⟺a\in {\Gamma }^{+}\text{ or }b\in {\Gamma }^{+}$) ($⟹$) Suppose $a\vee b\in {\Gamma }^{+}$. If $a\notin {\Gamma }^{+}$ and $b\notin {\Gamma }^{+}$, it follows that $\neg a,\neg b\in {\Gamma }^{+}$. Since $\{a\vee b,\neg a,\neg b\}⊢x$ and is a finite subset of ${\Gamma }^{+}$, $P({\Gamma }^{+})$ does not hold: contradiction. ($⟸$) Suppose that either $a\in {\Gamma }^{+}$ or $b\in {\Gamma }^{+}$. Take the former case. Suppose $a\vee b\notin {\Gamma }^{+}$. Hence $\neg (a\vee b)\in {\Gamma }^{+}$. Since $\{a,\neg (a\vee b)\}⊢x$ and is a finite subset of ${\Gamma }^{+}$, $P({\Gamma }^{+})$ does not hold: contradiction.

Therefore, ${\Gamma }^{+}$ is well-behaved in the sense of ^f6ac8d. By ^bc81d0, it follows that there exists a valuation $v_{{\Gamma }^{+}}$ such that ${\Gamma }^{+}=\{a\in \mathcal{L}:v_{{\Gamma }^{+}}(a)=1\}$. This means that $v_{{\Gamma }^{+}}({\Gamma }^{+})=1$. Moreover, note that $x\notin {\Gamma }^{+}$, for if $x\in {\Gamma }^{+}$, we have $\{x\}⊢x$ and clearly $\{x\}$ is a finite subset of ${\Gamma }^{+}$, violating $P({\Gamma }^{+})$. Since ${\Gamma }^{+}$ is well-behaved, $\neg x\in {\Gamma }^{+}$, and hence $v_{{\Gamma }^{+}}(\neg x)=1$, meaning $v_{{\Gamma }^{+}}(x)=0$. A fortiori, $v_{{\Gamma }^{+}}(\Gamma )=1$ and $v_{{\Gamma }^{+}}(x)=0$, for $\Gamma \subseteq {\Gamma }^{+}$. So, there exists a valuation function $v$ such that $v(\Gamma )=1$ and $v(x)=0$, i.e. $\Gamma ⊬x$. eproof