Model theory - Types and Model Construction

Types in Model Theory Introduction Types are one of the most important concepts in model theory. Intuitively, a type describes all the properties that a particular tuple of elements satisfies in a structure. By studying which types exist and which can be realized in a structure, we gain deep insight into the structure's behavior. This framework also allows us to construct new models with specific desired properties and understand relationships between different models. Complete Types Let's start with the fundamental definition. Suppose we have a structure $M$ and a tuple $\bar{a} = (a1, a2, \ldots, an)$ of elements from $M$. We also fix a set of parameters $A \subseteq M$ (which could be empty, or could contain elements we want to use in our formulas). The complete $n$-type of $\bar{a}$ over $A$, denoted $\text{tp}(\bar{a}/A)$, is simply the collection of all first-order formulas with parameters in $A$ that $\bar{a}$ satisfies. More precisely, it includes every formula $\phi(x1, \ldots, xn)$ with parameters from $A$ such that $M \models \phi(\bar{a})$. Why is this useful? A complete type tells us everything first-order logic can say about where a tuple is located in a structure, relative to the parameters $A$. Two tuples with the same complete type are indistinguishable from the perspective of first-order logic with parameters in $A$. The Automorphism Characterization Here's a crucial observation: two tuples $\bar{a}$ and $\bar{b}$ have the same complete type over $A$ if and only if there exists an automorphism of $M$ that fixes every element of $A$ pointwise and maps $\bar{a}$ to $\bar{b}$. This means types are intimately connected to the symmetries of the structure. If an automorphism leaving $A$ fixed can move $\bar{a}$ to $\bar{b}$, then $\bar{a}$ and $\bar{b}$ must satisfy exactly the same formulas over $A$. Partial Types and Completeness Not every set of formulas is a complete type. A partial type over $A$ is simply any set of formulas with parameters in $A$. It might be missing infinitely many formulas, or it might only be a small collection. A partial type is complete if it has the completeness property: for every formula $\phi(x1, \ldots, xn)$ with parameters in $A$, the partial type contains either $\phi$ or $\neg\phi$ (but not both). This means the partial type gives a definitive answer about every possible first-order statement. The key distinction: A complete type over $A$ is a maximal consistent set of formulas—it commits to a position on every first-order property. A partial type might only make commitments about some properties, leaving others undecided. Isolated Types Some types are special because they are determined by a single formula. A type $p$ is isolated if there exists a formula $\phi(x1, \ldots, xn)$ with parameters in $A$ such that: for every formula $\psi(x1, \ldots, xn)$ in $p$, the theory entails that $\phi$ implies $\psi$ (i.e., $\phi \vdash \psi$ modulo the theory). In other words, the single formula $\phi$ completely determines the type. Once we know a tuple satisfies $\phi$, we automatically know it satisfies every other formula in the type. Intuition: Isolated types are the "rigid" types—they are pinned down by a single property. Non-isolated types are more "generic"—no single property determines them completely. Properties of Structures: Atomic, Saturated, and Homogeneous Now we turn to properties of structures themselves, which are defined in terms of which types they realize. Atomic Structures A structure $M$ is atomic if every complete type it realizes over the empty set is isolated. This means that for every tuple $\bar{a}$ in $M$, there is some formula (without parameters) that completely determines the type of $\bar{a}$. Atomic structures are in some sense "rigid" and "well-understood"—there are no mysterious, generic elements floating around. Example: The real numbers $(\mathbb{R}, <)$ are atomic. Any tuple of real numbers has a type that can be isolated by a single formula describing the ordering relationships between them. Saturated Structures A structure $M$ is saturated if it realizes every type over any parameter set that is smaller than $M$ itself. More formally: for any set $A \subseteq M$ with $|A| < |M|$, every complete $n$-type over $A$ is realized by some tuple in $M$. This is a strong property: a saturated structure is "complete" in the sense that you can't find a missing type by looking at types over smaller sets of parameters. Example: The rational numbers $(\mathbb{Q}, <)$ form a saturated structure (when we consider them as countable). In contrast, the real numbers $(\mathbb{R}, <)$, though atomic, are not saturated as a countable structure—there exist countable parameter sets and types over them that are not realized in $\mathbb{R}$. Homogeneous Structures A structure $M$ is (strongly) homogeneous if the following property holds: whenever two tuples $\bar{a}$ and $\bar{b}$ have the same type over some small subset $A \subseteq M$ (say, where $|A|$ is small compared to $|M|$), there exists an automorphism of $M$ fixing $A$ pointwise that maps $\bar{a}$ to $\bar{b}$. In other words, if two tuples are indistinguishable by formulas with parameters in $A$, then they are actually conjugate by an automorphism fixing $A$. Homogeneous structures have a strong uniformity property: wherever you find a particular configuration, you can transform it to any other configuration with the same type via an automorphism. Stone Spaces Now we move to a more abstract, but powerful, perspective. For a fixed parameter set $A$, consider all the definable subsets of $M^n$ (that is, subsets of the form $\{\bar{a} \in M^n : M \models \phi(\bar{a})\}$ where $\phi$ is a formula with parameters in $A$). These definable subsets form a Boolean algebra: they are closed under union, intersection, and complementation. By Stone's representation theorem, we can represent this Boolean algebra geometrically using ultrafilters. The Stone space $Sn(A)$ consists of all the ultrafilters on this Boolean algebra of definable subsets. Each ultrafilter corresponds to exactly one complete $n$-type over $A$. Why? An ultrafilter picks out which definable subsets a "hypothetical" tuple "belongs to"—and this consistent choice determines a complete type. In this representation, the complete $n$-types over $A$ form a topological space (with the Stone topology), which gives us geometric intuition about the space of types. This perspective connects combinatorial properties of types to topological properties. The Omitting Types Theorem One of the most important theorems about types is the Omitting Types Theorem. Here's the countable version: If $T$ is a countable theory with only countably many complete types over the empty set, then there exists a countable model of $T$ that is atomic—that is, it realizes only the isolated types and omits all the non-isolated ones. Why does this matter? It guarantees that certain types don't "force" themselves to be realized. If a type is non-isolated, we can always find a model that avoids it. This is powerful because it shows that atomic models always exist under mild cardinality assumptions. Conversely, for any set of types over a fixed parameter set, there is always an elementary extension of a given model that realizes all of them. So types are democratically realizable in extensions—you can find models where any desired collection of types is realized. Ultraproducts and Łoś's Theorem The final major tool is the ultraproduct construction, which allows us to build new models from old ones. An ultraproduct of a family of structures $(Mi){i \in I}$ modulo an ultrafilter $U$ on the index set $I$ is constructed as follows: take the product $\prod{i \in I} Mi$, and define two tuples to be equivalent if they agree on a set of indices that belongs to the ultrafilter $U$. The ultraproduct is the quotient by this equivalence relation. When all the factors are the same structure $M$, we call this an ultrapower of $M$. Łoś's Theorem The key property of ultraproducts is Łoś's theorem: A first-order sentence $\phi$ holds in the ultraproduct if and only if the set of indices $i$ where $\phi$ holds in $Mi$ belongs to the ultrafilter $U$. More informally: a property is true in the ultraproduct when it is true "in most" of the factors (where "most" is defined by the ultrafilter). Consequences: An ultraproduct of models of a theory $T$ is again a model of $T$. Two structures are elementarily equivalent (i.e., satisfy the same first-order sentences) if and only if they have isomorphic ultrapowers. This shows that ultraproducts are a powerful way to transfer properties and construct new models with specified characteristics.