17. Compactness and its Applications

One of the immediate consequences of the Completeness and Soundness Theorems is a result called the Compactness Theorem for first-order logic. This result, in turn, has many applications in the analysis of first-order logic.

Compactness Theorem

Compactness Theorem. For any set $\Gamma$ of sentences and any sentence $\phi$, $\Gamma \vDash \phi$ if and only if there is a finite subset $\Gamma' \subseteq \Gamma$ for which $\Gamma' \vDash \phi.$

Proof. The $\Leftarrow$ direction of the theorem is obvious: if $\Gamma' \vDash \phi$ and $\Gamma \supseteq \Gamma'$, then every model $M$ of $\Gamma$ is also a model of $\Gamma'$ so it must satisfy $M \vDash \phi.$

For the other direction, consider any $\Gamma$ and $\phi$ for which $\Gamma \vDash \phi.$ By the Completeness Theorem, $\Gamma \vdash \phi.$ Consider a formal proof of $\phi$ that uses the set $\Gamma' \subseteq \Gamma$ of premises. Since a formal proof has finite length, $\Gamma'$ must also be finite. And the same proof shows that $\Gamma' \vdash \phi.$ By the Soundness Theorem, this implies that $\Gamma' \vDash \phi.$

There is another equivalent formulation of the Compactness Theorem in terms of satisfiability.

Corollary. A set $\Gamma$ of sentences is satisfiable if and only if every finite subset $\Gamma' \subseteq \Gamma$ is satisfiable.

A Term for Every Element?

Recall that the set $\Gamma_{\rm PA}$ of Peano axioms gives us a way to study arithmetic within first-order logic. Its signature includes the constant $0$, the unary successor function $S$, and the binary functions $+$ and $\times$.

Obviously, the constant $0$ can represent only one of the elements of any domain of a model of $\Gamma_{\rm PA}$, but it also contains infinitely many different terms $S(0)$, $S(S(0))$, $S(S(S(0)))$, etc. that each represent different elements of the domain. And in the standard model of arithmetic with domain $\mathbb{N}$, when we define $S(n) = n+1$ for each $n \in \mathbb{N}$ then every element of the domain is represented by a term in the language.

Is this property true of every model of $\Gamma_{\rm PA}$? Is every element of the domain always represented by a term?

No! And not only that, but we also can’t add any additional axioms to obtain a set $\Gamma'_{\rm PA}$ of axioms whose models all have that property—even if we add infinitely many of them. We can prove this result using the Compactness Theorem.

Theorem. For every set $\Gamma'_{\rm PA} \supseteq \Gamma_{\rm PA}$ of axioms, if $\Gamma'_{\rm PA}$ is satisfiable by a model $M$ with infinite domain, then there is a model $M'$ of $\Gamma'_{\rm PA}$ with at least one domain element that is not representable by terms.

Proof. Consider the extension of the signature $\sigma$ of Peano arithmetic where we add a second constant $c$. Define the set
\[\Delta = \{ \neg c = t : t \mbox{ is a closed term}\}\]
of axioms. We claim that $\Gamma'_{\rm PA} \cup \Delta$ is satisfiable. Indeed, any finite subset $\Sigma \subset \Gamma'_{\rm PA} \cup \Delta$ includes at most a finite number of the sentences in $\Delta$, there must be an element in the domain of $M$ that is not represented by any of the terms in those sentences. Consider the structure $M_\Sigma$ obtained by extending $M$ by assigning such an element to $c$. This structure is a model of $\Sigma$. Therefore, by the Compactness Theorem, there exists a model $M'$ of $\Gamma'_{\rm PA} \cup \Delta$ itself. The restriction of $M'$ to the signature of Peano arithmetic then contains an element in its domain (the one that was assigned to $c$ in the larger signature) that is not represented by any term.

Domain Sizes: Lower Bounds

Can a first-order language enforce any conditions on the size of the domain of its models? For Peano arithmetic, for example, we might want to enforce the condition that the only models for it have countably infinite cardinality so that we really are considering only models of arithmetic over $\mathbb{N}$-like domains. Or in other settings (for example when formalizing the study of finite groups), we might want to have axioms that force the models of the theory to have finite domains of a fixed size.

Let’s examine a few special cases of this question. By definition, we already know that the domain of any model must be non-empty, so it contains at least one element. Can we define an axiom that is only satisfied by models which have at least 2 elements in their domain? Yes! Consider

\[\forall x_1 \exists x_2 \, \neg x_1=x_2.\]

What about forcing models to have at least $k$ elements for some $k \ge 2$? We can do that too. Consider the sentence $\phi_{\ge k}$ defined by

\[\forall x_1 \forall x_2 \cdots \forall x_{k-1} \exists x_k ( \neg x_k = x_1 \wedge \neg x_k = x_2 \wedge \cdots \wedge \neg x_k = x_{k-1} ).\]

What about requiring the domain to be infinite? We can do this too, by adding the infinite set of sentences $\{ \phi_{\ge k} : k \in \mathbb{N}\}$ to the set of axioms.

So far so good! So we may as well go one step further: is it also possible to require models of a theory to have domains that are uncountable? (For example, if we want a theory of the real numbers.)

No, we can’t. This result represents half of the Löwenheim-Skolem Theorem.

Downward Löwenheim-Skolem Theorem. Every satisfiable set $\Gamma$ of axioms in first-order logic over a countable signature has a model with a finite or countably infinite domain.

Proof. By the Soundness Theorem, since $\Gamma$ is satisfiable then it is also consistent. And in the proof of the Completeness Theorem, we have seen that when $\Gamma$ is consistent, then it is satisfied by the restriction $M^-$ of the factored term model $M_{\Gamma^+}^\approx$ of the extension of $\Gamma^+$ obtained by adding one constant $c_x$ to each variable $x$ to the signature of $\Gamma$. But as we saw in the definition of factored term models, $M^-$ and $M_{\Gamma^+}^\approx$ have at most countably many elements in their domains.

Domain Sizes: Upper Bounds

We can also ask about whether sets of axioms can give upper bounds on the size of domains of their models.

We can construct a simple sentence that is only satisfied by structures with domains that contain only a single element:

\[\exists x \forall y \, x = y\]

And we can construct a sentence that is only satisfied by structures whose domains have at most 2 elements.

\[\exists x_1 \exists x_2 \forall y \, (y = x_1 \vee y = x_2).\]

Similarly, for every $k \in \mathbb{N}^+$ we can construct a sentence $\phi_{\le k}$ that is satisfied only by structures with domains of cardinality at most $k$:

\[\exists x_1 \exists x_2 \cdots \exists x_k \forall y \, (y = x_1 \vee y = x_2 \vee \cdots \vee y = x_k).\]

Note that we can now also define $\phi_{=k} = \phi_{\ge k} \wedge \phi_{\le k}$ to obtain an axiom whose models all have domains that contain exactly $k$ elements.

Continuing along the same path that we followed in the last section, can we now define a sentence that is satisfied only by models of finite (but arbitrarily large) domains?

No!

Theorem. If $\Gamma$ is satisfied by models with domains of size at least $n$ for any $n \in \mathbb{N}$, then $\Gamma$ is also satisfied by a model with an infinite domain.

Proof. The condition on $\Gamma$ guarantees that for any $n \in \mathbb{N}$, the set $\Gamma \cup \{\phi_{\ge n}\}$ is satisfiable. And for any $m < n$, all structures that satisfy $\phi_{\ge n}$ also satisfy $\phi_{\ge m}$. So for any finite set $I \subseteq \mathbb{N}$, the set $\Gamma \cup \bigcup_{n \in I} \{\phi_{\ge n}\}$ is satisfiable. By the Compactness Theorem, this means that the set
\[\Gamma \cup \bigcup_{n \in \mathbb{N}^+} \{\phi_n\}\]
is also satisfiable. Let $M$ be a structure that satisfies this set of axioms. The domain of $M$ must be infinite, since otherwise there is some value $n \in \mathbb{N}$ for which $M \not\vDash \phi_{\ge n}$.

What about sets of axioms whose models have domains with at most countably many elements? We can’t do that either, and this forms the other half of the Löwenheim-Skolem Theorem.

Upward Löwenheim-Skolem Theorem. If $\Gamma$ has a model with infinite domain, then it has models of arbitrarily large infinite cardinality $\kappa$.

Proof. This strengthening of the last theorem is obtained by applying a slight twist to its argument. Consider the extension of the signature $\sigma$ of $\Gamma$ where we add $\kappa$ new constants. Let $\Delta$ consists of the (possibly uncountably many!) sentences $\neg c_\alpha = c_\beta$ for each $\alpha \neq \beta$ in the set of indices of cardinality $\kappa$. Define $\Gamma' = \Gamma \cup \Delta$. Every model of $\Gamma'$ has a domain of cardinality at least $\kappa$. And there does exist such a model $M$ by the Compactness Theorem since any finite subset of $\Gamma'$ includes only a finite number of the sentences in $\Delta$ and so there is an extension of a model of $\Gamma$ that also satisfies those sentences. Finally, the restriction of $M$ to the original signature $\sigma$ gives the desired model of $\Gamma$ with domain size at least $\kappa$.