Notes - Logic and Proof MT24, Compactness theorems

A function

\[v : D \to \\{0, 1\\}\]

where $D$ is either the infinite set $\{p _ 1, \ldots, p _ n\}$ or a finite initial segment $\{p _ 1, \ldots, p _ n\}$.

\[\text{dom}(v) \subseteq \text{dom}(v')\]

and

\[v[p_i] = v'[p_i]\]

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

Overall idea: The only tricky direction is finding a satisfying assignment for all of $F$ given that every finite subset is satisfiable. First you show that for every $n$, there is a satisfying assignment for all formulas on propositional variables $p _ 1, \ldots, p _ n$. Then you show that you can build up a sequence of assignments $v _ 0, v _ 1, \ldots, v _ n$ where each assignment agrees with all the previous ones. Then you define a “global” assignment $v^\ast$ by $v^\ast(p _ n) = v _ n(p _ n)$.

---

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 good partial assignment with formulas that mention only propositional variables $p _ 1, p _ 2, \ldots, p _ n$.

To see this, 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 maintain the invariant that there are infinitely many good partial assignments that extend $v _ n$.

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 invariant. Consider the two assignments extending $v _ n$ given by $v _ n^0, v _ n^1$ that extend $v _ n$ by either setting $p _ {n+1}$ to $0$ or $1$. Since any proper extension of $v _ n$ is an extension of either $v _ n^0$ or $v _ n^1$, it follows that at least one of them has infinitely many good extensions. Let $v _ {n+1}$ be $v _ n^0$ or $v _ n^1$ 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.

Suppose:

• $\sigma$ is a countable signature
• $\pmb S$ is a set of $\sigma$-formulas

Then:

• Every finite subset of $\pmb S$ has a model iff $\pmb S$ has a countable model.

Clearly if $\pmb S$ has a countable model, then every finite subset of $\pmb S$ has a model.

For the other direction, by replacing the free variables in the formulas in $\pmb S$ by constant symbols, we may assume without loss of generality that $\pmb S$ consists entirely of sentences.

For each sentence $F \in \pmb S$, let $F’$ be its skolemization, and write $\pmb S’ := \{F’ : F \in \pmb S\}$. Then every finite subset of $\pmb S’$ is satisfiable.

It follows that each finite subset of

\[\bigcup_{F' \in \pmb S'} E(F')\]

is also satisfiable by Herbrand’s theorem (given a finite subset of this set, pick the satisfying assignment that works for all the sentences that the Herbrand expansion comes from).

But by the compactness theorem for propositional logic, we have that $\bigcup _ {F’ \in \pmb S’} E(F’)$ is satisfiable. Therefore $\pmb S’$ has a (countable) Herbrand model, and we are done.

Suppose such a formula exists.

For all $n \in \mathbb N$, let $\psi _ n(x, y)$ be a formula expressing that there is a path from $x$ to $y$ of length $n$.

Now define

\[\pmb S := \\{ \phi(x, y) \\} \cup \\{\lnot \psi_n(x, y) \mid n \in \mathbb N\\}\]

Then every finite subset of $\pmb S$ is satisfiable whereas $\pmb S$ is not satisfiable (in other words, there are graphs where two vertices are separated by an arbitrary distance path, but there are no graphs where two vertices are connected despite not being connected by a path of arbitrary distance).

This contradicts compactness, hence no such $\phi(x, y)$ can exist.