Notes - Logic and Proof MT24, Compactness theorem

and

for all $p _ i \in \text{dom}(v)$.

Suppose:

• $S$ is a set of formulas (possibly infinite)

Then:

• $S$ is satisfiable if and only if every finite subset of $S$ is satisfiable

Forward direction: If $S$ is satisfiable then every finite subset has to be satisfiable.

Backward direction: Let $S$ be a set of formulas such that every finite subset of $S$ is satisfiable.

Say a partial assignment $v$ is “good” if it satisfies any formula $F \in S$ that only mentions propositional variables in the domain of $v$.

Note that for each $n \in \mathbb N$, there is a partial assignment $v$ with formulas that mention only propositional variables $p _ 1, p _ 2, \ldots, p _ n$. Consider a subset $S’ \subseteq S$ that only mentions formulas on propositional variables $p _ 1, \ldots, p _ n$.

$S’$ might be infinite, but it can only contain finitely many formulas up to logical equivalence.

Since all finite subsets of $S$ are satisfiable, it follows $S’$ is satisfiable by a partial assignment $v$, and by construction this assignment is good.

Now we construct a sequence of good partial assignments $v _ 0, v _ 1, \ldots$ with $\text{dom}(v _ n) = \{p _ 1, \ldots, p _ n\}$ where $v _ {n+1}$ extends $v _ n$ for each $n$ and the inductive hypothesis that there are infinitely many good partial assignments that extend $v _ n$.

To do this, take $v _ 0$ to be the assignment with an empty domain. Since there is a good assignment with domain $\{p _ 1, \ldots, p _ n\}$ for every $n$, there are infinitely many good assignments that extend $v _ 0$. So the inductive hypothesis is satisfied.

Now suppose we have constructed assignments $v _ 0, \ldots, v _ n$ all satisfying the inductive hypothesis. Take two assignments $v, v’$ that extend $v _ n$ with $\text{dom}(v) = \text{dom}(v’) = \{p _ 1, \ldots, p _ {n+1}\}$. Since any proper extension of $v _ n$ is an extension of either $v$ or $v’$, it follows that one (or both) of $v$ and $v’$ have infinitely mnay good extensions. Let $v _ {n+1}$ be $v$ or $v’$ depending on which satisfies this property, and therefore the inductive hypothesis is satisfied.

Now define a total assignment $v[p _ n] := v _ n[p _ n]$ for each $n \in \mathbb N$. Then $v$ satisfies all formulas in $S$, since for any formula in $S$ that contains $n$ propositional variables $\{p _ 1, \ldots, p _ n\}$, $v _ n$ satisfies $F$. Since $v$ extends $v _ n$, it follows $v$ satisfies $F$ also.