Core Foundations of Model Theory

Introduction to Model Theory What is Model Theory? Model theory is the study of how formal mathematical theories relate to their models—the concrete structures where the theory's statements are true. Think of it this way: a formal theory is like a set of rules or axioms written in a formal logical language, and a model is any mathematical structure that satisfies all those rules. The key questions model theorists ask are: How many models does a theory have, and how large can they be? What relationships exist between different models of the same theory? Which sets of elements inside a model can be described using the theory's language? This focus on structures and interpretations makes model theory fundamentally semantic—it's about meaning and truth in concrete structures, rather than just about formal symbolic manipulation. <extrainfo> Compared to proof theory, which focuses on formal derivations and is purely syntactic (manipulating symbols according to rules), model theory is more closely connected to classical mathematics and how mathematicians actually think about structures. </extrainfo> First-Order Logic: The Language of Model Theory Building Blocks Model theory primarily uses first-order logic as its formal language. Here's how it works: Atomic formulas are the basic building blocks—statements like $P(x)$ (a relation holds for $x$) or $f(x) = y$ (a function has a particular value). From these simple pieces, we build more complex formulas using: Boolean connectives: $\neg$ (not), $\land$ (and), $\lor$ (or), $\rightarrow$ (if...then) Quantifiers: $\forall$ (for all) and $\exists$ (there exists) For example, $\forall x \, (P(x) \rightarrow Q(x))$ means "for all $x$, if $P(x)$ holds then $Q(x)$ holds." A sentence is a special kind of formula where every variable is bound by a quantifier—there are no free variables. This matters because sentences express complete thoughts that can be true or false in a structure. Truth and Satisfiability Tarski's definition of truth provides a rigorous way to determine whether a formula is true in a given structure. This is captured by the satisfaction relation $\models$: we write $\mathcal{M} \models \phi$ to mean "structure $\mathcal{M}$ satisfies (makes true) the formula $\phi$." A theory is simply a set of sentences that serve as axioms. For instance, the axioms of group theory form a theory. The real power appears when we ask: does a theory have any models at all? A theory is satisfiable if at least one structure makes all its sentences true. A theory is complete if, for every sentence in the language, either the sentence or its negation belongs to the theory. (Complete theories "decide" every statement.) Gödel's completeness theorem connects semantic truth to logical provability: a theory is satisfiable if and only if it is consistent (cannot derive a contradiction using logical rules). In other words, if a theory has no logical contradictions, then it has a model. Core Definitions: Signatures, Structures, and Substructures Signatures and Structures Before we can talk about any particular theory, we must specify the signature (also called language)—the collection of non-logical symbols we're allowed to use. A signature consists of: Constant symbols (elements like $0$, $1$) Function symbols (operations like $+$, $\times$, with specified arities) Relation symbols (properties like $<$, $=$ with specified arities) For example, the signature of arithmetic includes the constant $0$, the functions $+$ and $\times$, and the relation $<$. A structure (or model) for a given signature consists of: A non-empty domain (set of elements we're talking about) Interpretations of all the symbols—assigning concrete meanings A structure models a set of sentences if all those sentences evaluate to true under the given interpretations. Substructures and Elementary Substructures Sometimes we have a structure and want to consider a smaller one inside it. A substructure is a subset of the domain that is closed under all the functions in the signature and inherits the relations. For instance, the integers are a substructure of the real numbers with the standard signature for arithmetic. However, closure and inheritance aren't always enough. An elementary substructure is stronger: it preserves the truth of every first-order formula, not just the base relations. This is crucial because a substructure might satisfy some sentences but not others. An elementary embedding is an injective (one-to-one) homomorphism whose image is an elementary substructure. It's a way to embed one structure into another while perfectly preserving all first-order properties. Reducts and Expansions Often we want to compare structures with different signatures. A reduct of a structure "forgets" some symbols—we simply stop interpreting them. Conversely, an expansion adds new symbols to the signature and provides interpretations for them. These operations allow us to study how theories change when we add or remove the ability to express certain concepts. Two Fundamental Theorems: Compactness and Löwenheim–Skolem The Compactness Theorem The compactness theorem is a cornerstone result: if every finite subset of a set of sentences is satisfiable, then the entire set is satisfiable. Why does this matter? It means we can check satisfiability by checking finite pieces. More usefully, by contrapositive: if a theory is unsatisfiable (has no models), then there must be some finite subset of sentences that is already unsatisfiable. We never need infinitely many axioms to get a contradiction—finitely many will do. The Löwenheim–Skolem Theorem The Löwenheim–Skolem theorem reveals something surprising about cardinality and models. It has two directions: Downward direction: Any infinite structure in a countable signature has a countable elementary substructure. This is striking—even if we're studying an enormous structure (like the real numbers, which is uncountable), we can find a countable "snapshot" that preserves all first-order properties. Upward direction: For any infinite cardinal $\kappa$, any structure of size less than $\kappa$ can be elementarily embedded into a structure of size $\kappa$. So if a theory has any infinite models, we can build models of arbitrarily large size. The combined consequence: Any theory with infinite models in a countable signature has both countable models and models of every infinite cardinality. This means a single theory can have models of wildly different sizes—all while preserving first-order properties. These theorems reveal that first-order logic is inherently "coarse"—it cannot distinguish between structures that differ only in size or have infinitely many elements. This limitation is fundamental to understanding what first-order theories can and cannot express.