Compactness Theorem/Proof using Ultraproducts

From ProofWiki
Jump to navigation Jump to search


Let $\LL$ be the language of predicate logic.

Let $T$ be a set of $\LL$-sentences.

Then $T$ is satisfiable if and only if $T$ is finitely satisfiable.


By definition, $T$ is finitely satisfiable means that every finite subset of $T$ is satisfiable.

Because the direction:

$T$ satisfiable implies $T$ finitely satisfiable

is trivial, the proof below justifies the converse:

$T$ finitely satisfiable implies $T$ satisfiable.

The idea is to construct an ultraproduct using a purposefully selected ultrafilter and collection of models so that each sentence in $T$ will be realized as a result of Łoś's Theorem.

Let $\Sigma$ be the set of all finite subsets of $T$.

For every $\Sigma_0 \in \Sigma$, define:

$F_{\Sigma_0} = \set {\Delta \in \Sigma: \Sigma_0 \subseteq \Delta}$

That is, $F_{\Sigma_0}$ is the collection of all finite subsets of $T$ including $\Sigma_0$.

Clearly $F_{\Sigma_0}$ is a subset of $\Sigma$.

Now define:

$F = \set {F_{\Sigma_0}: \Sigma_0 \in \Sigma}$

a subset of $\powerset \Sigma$.

We claim this has the finite intersection property.

Take any finite collection $\ds \set {F_{\Sigma_k} }_{k = 1, 2, \dots, n}$ of elements on $F$, and observe that the set $\ds S = \bigcup_{k \mathop = 1}^n \Sigma_k$ is a finite subset of $T$.

That is, $S \in \Sigma$.

$S \in F_{\Sigma_k}$ for each $k$ by construction, and hence is in their intersection.

In fact, their intersection is $F_S$.

So the intersection of any finite collection of elements of $F$ is nonempty as claimed.

Since $F$, which is a set of subsets of $\Sigma$, has the finite intersection property, there is an ultrafilter $U$ on $\Sigma$ including it (by the corollary to the Ultrafilter Lemma).

If $\Sigma_0 \in \Sigma$, then by assumption it has a model $\AA_{\Sigma_0}$.


$\ds \AA = \paren {\prod_{\Sigma_k \mathop \in \Sigma} \AA_{\Sigma_k} } / U$

We verify $\AA \models T$.

Take any $\phi \in T$.

Observe that $F_{\set \phi} \in U$ by definition of $U$.

Furthermore, if we define $\Phi = \set {\Sigma_0 \in \Sigma: \AA_{\Sigma_0} \models \phi}$, we have $F_{\set \phi} \subseteq \Phi$.

Hence, since $U$ is a filter and $F_{\set \phi} \in U$, $\Phi \in U$.

Then Łoś's Theorem implies that $\AA \models \phi$.