Propositional Logic - Applications

TheoremCompactness Theorem

A set $\Gamma$ of propositional formulas is satisfiable (has a model) if and only if every finite subset of $\Gamma$ is satisfiable.

Formally: $\Gamma$ has a truth assignment making all formulas true if and only if every finite $\Delta \subseteq \Gamma$ has such a truth assignment.

The compactness theorem is remarkable because it allows us to conclude facts about infinite sets from properties of their finite subsets. For propositional logic, the proof is straightforward (since we can only have finitely many propositional variables in any finite subset), but the theorem generalizes to first-order logic where it has profound implications.

ExampleApplication to Graph Coloring

Consider the problem of $k$ -coloring an infinite graph $G = (V, E)$ where $V$ is infinite. We can encode this as a propositional satisfiability problem:

For each vertex $v \in V$ and color $i \in \{1, \ldots, k\}$ , create a variable $p_{v,i}$ meaning "vertex $v$ has color $i$ "
Add formulas ensuring each vertex has exactly one color
Add formulas $\neg(p_{v,i} \land p_{w,i})$ for each edge $(v,w)$ and color $i$

If every finite subgraph of $G$ is $k$ -colorable, then every finite subset of these formulas is satisfiable. By compactness, the entire infinite set is satisfiable, yielding a $k$ -coloring of the infinite graph $G$ .

TheoremDeduction Theorem

For any set of formulas $\Gamma$ and formulas $\phi$ , $\psi$ :

\Gamma \cup \{\phi\} \vdash \psi \quad \text{if and only if} \quad \Gamma \vdash \phi \to \psi

The deduction theorem justifies the common proof technique of assuming a hypothesis and deriving a conclusion, then concluding the implication is provable. This meta-theorem about the proof system itself simplifies many logical arguments.

ExampleUsing the Deduction Theorem

To prove $(p \to q) \land (q \to r) \vdash p \to r$ :

Assume $p$ (add to premises)
From $p \to q$ and $p$ , derive $q$
From $q \to r$ and $q$ , derive $r$
We've shown $(p \to q) \land (q \to r), p \vdash r$
By the deduction theorem, $(p \to q) \land (q \to r) \vdash p \to r$

Without the deduction theorem, we would need to construct a direct proof of the implication, which is more cumbersome.

Remark

These theorems demonstrate the rich structure of propositional logic despite its apparent simplicity. The compactness theorem connects finite and infinite, while the deduction theorem bridges syntactic proof manipulation and semantic consequence. Both extend to first-order logic, where they become even more powerful and find applications across mathematics.

These results are not merely theoretical curiosities but practical tools used in automated reasoning, formal verification, and the foundations of computer science.