Compactness, Types, and the Architecture of First-Order Theories

I. Compactness and the Upward Löwenheim–Skolem Theorem

The Construction of Elementary Extensions

The Compactness Theorem serves as the primary engine for model-theoretic constructions, allowing us to build structures that satisfy arbitrary sets of consistent first-order axioms.

Theorem (Upward Löwenheim–Skolem): Let $T$ be an $L$-theory with an infinite model $\mathcal{M}$. For every cardinal $\kappa \ge \max (|L|,{\aleph }_0)$, there exists a model $\mathcal{N}$ of $T$ such that $\mathcal{M}⪯\mathcal{N}$ and $|\mathcal{N}|\ge \kappa$.

Proof: Let $\mathcal{M}$ be an infinite model of $T$ with domain $M$. We construct an elementary extension using the elementary diagram of $\mathcal{M}$. Let $L_M=L\cup \{c_m:m\in M\}$ be an expansion of the language $L$ where each element $m\in M$ is named by a unique constant symbol $c_m$. The elementary diagram of $\mathcal{M}$, denoted $Dia{g}_{el}(\mathcal{M})$, is the set of all $L_M$-sentences true in $\mathcal{M}$.

To construct a model of cardinality $\kappa$, we expand $L_M$ further to $L^{\prime }=L_M\cup \{d_{\alpha }:\alpha <\kappa \}$, where $\{d_{\alpha }{\}}_{\alpha <\kappa }$ is a set of new constant symbols. Consider the theory $\Gamma =Dia{g}_{el}(\mathcal{M})\cup \{d_{\alpha }\ne d_{\beta }:\alpha <\beta <\kappa \}$.

We claim $\Gamma$ is finitely satisfiable. Let ${\Gamma }_0\subseteq \Gamma$ be a finite subset. ${\Gamma }_0$ contains a finite number of new constants $\{d_{{\alpha }_1},\dots ,d_{{\alpha }_n}\}$. We can satisfy ${\Gamma }_0$ by expanding $\mathcal{M}$ to a model of $L^{\prime }$ where we interpret the constant symbols $c_m$ as the elements $m\in M$, and interpret the $d_{{\alpha }_i}$ as distinct elements in $M$ (possible because $M$ is infinite). By the Compactness Theorem, the full theory $\Gamma$ is satisfiable. Let $\mathcal{N}$ be a model of $\Gamma$. Since $\mathcal{N}\models Dia{g}_{el}(\mathcal{M})$, there exists an elementary embedding $h:\mathcal{M}\hookrightarrow \mathcal{N}$ (the Diagram Lemma). Thus, $\mathcal{M}⪯\mathcal{N}$. Finally, the axioms $\{d_{\alpha }\ne d_{\beta }\}$ ensure that the set $\{d_{\alpha }^{\mathcal{N}}:\alpha <\kappa \}$ has cardinality at least $\kappa$, implying $|\mathcal{N}|\ge \kappa$.

The Limits of Expression: Zooming In and Out

The Downward and Upward Löwenheim–Skolem theorems define the "cardinality bounds" of first-order logic. The Downward LS Theorem asserts that if a theory has an infinite model, it has a countable elementary substructure (provided $|L|={\aleph }_0$), allowing us to "zoom in" on a structure to find its countable essence. The Upward LS Theorem allows us to "zoom out," constructing models of arbitrary size.

A quintessential example is the theory of Peano Arithmetic ($PA$). The standard model $\mathbb{N}\models PA$ is countable. By the Upward LS theorem, there exist elementary extensions $\mathcal{N}\succ \mathbb{N}$ such that $|\mathcal{N}|>{\aleph }_0$. These "non-standard" models contain infinite elements greater than every standard natural number $n\in \mathbb{N}$. It is important to note that while $\mathbb{N}\prec \mathcal{N}$ holds for these specific extensions, it is not the case that $\mathbb{N}$ is an elementary substructure of every model of $PA$; rather, these models demonstrate that $PA$ cannot force a domain to be exactly $\mathbb{N}$ in first-order logic.

II. Stone Spaces and the Syntax-Semantics Interface

While Part I demonstrated how models grow, Part II examines how types control that growth. The structure of a theory is mirrored by its Stone space, which effectively maps the "syntax" (formulas) to the "semantics" (realizable sets of formulas).

Topology on the Stone Space $S_n(T)$

Let $S_n(T)$ be the set of complete $n$-types over $T$. For any $L$-formula $\varphi (\bar{x})$, we define the set $[\varphi ]=\{p\in S_n(T):\varphi \in p\}$. The collection $\{[\varphi ]:\varphi \in L\}$ forms a basis for the topology on $S_n(T)$.

1. Hausdorff: If $p\ne q$, there exists a formula $\varphi$ such that $\varphi \in p$ and $\varphi \notin q$. Thus $\neg \varphi \in q$. The sets $[\varphi ]$ and $[\neg \varphi ]$ are disjoint open sets containing $p$ and $q$, respectively.

2. Compactness: If $\{[{\varphi }_i]:i\in I\}$ is an open cover of $S_n(T)$, then ${\bigcap }_{i\in I}[\neg {\varphi }_i]=\varnothing$. This implies $T\cup \{\neg {\varphi }_i:i\in I\}$ is inconsistent. By the Compactness Theorem, some finite subset is inconsistent, implying ${\bigcup }_{i\in I_0}[{\varphi }_i]=S_n(T)$.

3. Totally Disconnected: Each $[\varphi ]$ is a clopen set because its complement is $[\neg \varphi ]$, which is also open. The existence of a basis of clopen sets confirms the space is zero-dimensional.

Categoricity, Saturation, and Atomic Models

The Stone space encodes the "variety" of models a theory can have. The connection between types and models is mediated by saturation and atomicity.

• Categoricity: Morley’s Categoricity Theorem states that if a countable first-order theory $T$ is $\kappa$-categorical for some uncountable cardinal $\kappa$, then it is $\lambda$-categorical for all uncountable cardinals $\lambda$. This reflects an underlying structural uniformity.

• $\omega$-Categoricity: By the Ryll-Nardzewski Theorem, a countable theory $T$ is ${\aleph }_0$-categorical if and only if $S_n(T)$ is finite for every $n<\omega$. In such theories, every type is isolated (the "predictable" points in the topology).

• Saturation: A model is $\kappa$-saturated if it realizes all types over sets of size $<\kappa$. Uncountably categorical theories are characterized by their saturated models in uncountable cardinalities.

• Atomic Models: Atomic models are models that omit all non-isolated types. They are the "simplest" possible structures in a theory. In theories with a dense set of isolated types, we can often construct an atomic model by realizing only those types that are "forced" by the theory.

The interplay between these concepts is fundamental: theories with few types in their Stone space (e.g., ${\aleph }_0$-categorical theories) are highly structured, while theories with complex, non-isolated types (e.g., those with the Independence Property or Order Property) lead to a wide spectrum of non-isomorphic models. By studying $S_n(T)$, we do not just study sets of formulas; we study the categorical limits of the theory itself.