Introduction to Model Theory

Fundamentals of Model Theory Introduction Model theory bridges two fundamental aspects of mathematics: the formal, symbolic world of logic and the concrete world of mathematical structures. At its heart, model theory asks a simple but profound question: Given a formal language, what mathematical objects can we describe with it, and how can we study those objects through their relationship with the language? This interplay between syntax (the form of logical statements) and semantics (their meaning in concrete structures) gives model theory its power. Understanding this correspondence allows us to translate difficult problems about logical deduction into problems about mathematical structures—and vice versa. What Is a Language in Model Theory? A language in model theory is a set of symbols that allows us to write formal statements. Think of it as the vocabulary and grammar we need to describe mathematical objects precisely. Every language contains two types of symbols: Logical symbols are the same in every language. These include: Logical connectives: "and" ($\land$), "or" ($\lor$), "not" ($\neg$) Quantifiers: "for all" ($\forall$) and "there exists" ($\exists$) Equality ($=$) and parentheses Non-logical symbols vary depending on what we want to study. These include: Constant symbols: These name specific objects (like the constant $0$ in arithmetic, or the constant $e$ in group theory) Function symbols: These name operations (like $+$ and $\times$ in arithmetic, or $\circ$ for composition in group theory) Relation symbols: These name relationships between objects (like $<$ for ordering, or $\in$ for membership) Example: The language of arithmetic includes the constant symbols $0$ and $1$, the function symbols $+$ and $\times$, and the relation symbol $<$. Using these symbols, we can write statements like "$\forall x \, (x + 0 = x)$" (all numbers added to zero equal themselves). The key insight is that a language by itself is just notation—it has no meaning until we interpret its symbols in a concrete mathematical structure. Structures: Giving Meaning to Languages A structure (also called a model) is a concrete mathematical object that gives meaning to the symbols of a language. Formally, a structure consists of: A non-empty domain: a specific set $D$ that serves as the universe of objects we're discussing Interpretations of constant symbols: each constant symbol is assigned a specific element of $D$ Interpretations of function symbols: each $n$-ary function symbol is assigned an actual function that takes $n$ elements from $D$ and outputs an element of $D$ Interpretations of relation symbols: each $n$-ary relation symbol is assigned a set of $n$-tuples from $D$ Example: Consider the language of arithmetic with symbols $0, 1, +, \times, <$. We could interpret this language in different ways: The standard model: Let $D$ be the set of natural numbers $\mathbb{N}$. Interpret $0$ as the number zero, $1$ as the number one, $+$ as addition, $\times$ as multiplication, and $<$ as the usual less-than relation. An alternative model: Let $D$ be the set of even numbers $\{0, 2, 4, 6, \ldots\}$. Interpret $0$ as zero, $1$ as... wait, this fails! The number one is not in our domain, so we cannot interpret $1$ in this structure. This shows that the same language can work naturally in some structures but not others. The notation $\mathcal{M}$ typically denotes a structure, and $|\mathcal{M}|$ denotes its domain. Satisfaction: When Formulas Are True Now that we have a language and a structure, we can ask: Is a particular sentence true in this structure? A sentence is a formula with no free variables—essentially, a complete statement that can be evaluated as true or false. We say a sentence $\varphi$ is satisfied by a structure $\mathcal{M}$ (written $\mathcal{M} \models \varphi$, read "$\mathcal{M}$ models $\varphi$") when the sentence is true under the given interpretations. Example: In the standard model of arithmetic, the sentence "$\forall x \, (x + 0 = x)$" is true, so we write $\mathbb{N} \models \forall x \, (x + 0 = x)$. However, the sentence "$\forall x \, (x > 0)$" is false in this structure (because $0$ is not greater than $0$), so we write $\mathbb{N} \not\models \forall x \, (x > 0)$. The truth of complex formulas is determined recursively: $\mathcal{M} \models (\varphi \land \psi)$ if both $\varphi$ and $\psi$ are satisfied by $\mathcal{M}$ $\mathcal{M} \models \forall x \, \varphi(x)$ if $\varphi(a)$ is satisfied for every element $a$ in the domain of $\mathcal{M}$ And so on for the other logical connectives and quantifiers Theories and Their Models A theory is a set of sentences that are all true in the same structure (or structures). It represents a collection of axioms—fundamental truths about some domain. For example: The theory of groups is the set of axioms that define group structure (associativity, identity element, inverses) The theory of ordered fields is the set of axioms defining real-number-like structures Peano arithmetic is the theory of natural numbers The models of a theory are precisely those structures that satisfy every sentence in the theory. In symbols, if $T$ is a theory, then $\mathcal{M}$ is a model of $T$ (written $\mathcal{M} \models T$) if $\mathcal{M} \models \varphi$ for every sentence $\varphi$ in $T$. A fundamental question in model theory is: Given a theory, how many different models does it have? What do those models look like? The answer reveals deep connections between logic and mathematics. The Syntactic Side and the Semantic Side One of the most powerful insights of model theory is recognizing that logical reasoning can be viewed from two complementary perspectives: The semantic side focuses on structures and truth: We ask: "Is this sentence true in this structure?" We study properties of actual mathematical objects We think about interpretations and domains The syntactic side focuses on formal proofs and derivations: We ask: "Can we prove this sentence from these axioms?" We study the logical rules that let us manipulate formulas We think about symbol manipulation without worrying about meaning The profound insight is that these two sides are deeply connected. A sentence that can be proved from a theory (syntactic) will be true in all models of that theory (semantic), and conversely. This connection between proof and truth is the subject of the Completeness Theorem, which we'll encounter later. Why does this matter? Translating a problem from one side to the other often makes it easier to solve. If a problem seems hard to prove syntactically, we might shift to the semantic perspective and study the structures directly. If a structural problem seems hard to analyze, we might encode it as logical statements and use proof techniques. Elementary Embeddings: Preserving Logical Structure When we have two structures, we often want to understand how they relate to each other. An elementary embedding is a particularly nice kind of relationship. An elementary embedding from a structure $\mathcal{M}$ to a structure $\mathcal{N}$ is a map $f: |\mathcal{M}| \to |\mathcal{N}|$ that: Is injective (one-to-one) Respects the interpretations of constant and function symbols Preserves the truth of all formulas in the language The last property is crucial: for any formula $\varphi(x1, \ldots, xn)$ and elements $a1, \ldots, an$ from $\mathcal{M}$, we have $$\mathcal{M} \models \varphi(a1, \ldots, an) \iff \mathcal{N} \models \varphi(f(a1), \ldots, f(an))$$ This means that any property expressible in the language that holds in $\mathcal{M}$ will also hold in $\mathcal{N}$ (via the embedding). Elementary embeddings are therefore very special—they allow us to transfer knowledge from one structure to another. Intuition: An elementary embedding is not just a structure-preserving map; it's a map that preserves every logical property of the source structure in the target structure. Elementary Equivalence: Same Logical Sentences Two structures can be quite different as mathematical objects yet satisfy exactly the same logical sentences. This phenomenon is captured by the concept of elementary equivalence. Two structures $\mathcal{M}$ and $\mathcal{N}$ are elementarily equivalent (written $\mathcal{M} \equiv \mathcal{N}$) if they satisfy exactly the same sentences of the language: $$\text{For all sentences } \varphi, \quad \mathcal{M} \models \varphi \iff \mathcal{N} \models \varphi$$ In other words, every statement you can make in the language is true in $\mathcal{M}$ if and only if it's true in $\mathcal{N}$. Example: Consider two different ordered fields: the rational numbers $\mathbb{Q}$ and the real numbers $\mathbb{R}$. These are very different as sets and as algebraic structures (the reals are complete; the rationals are not). However, in the language of ordered fields (which cannot express completeness), they satisfy the same first-order sentences. Therefore $\mathbb{Q} \equiv \mathbb{R}$ in first-order logic. Important distinction: Elementary equivalence ($\equiv$) is weaker than isomorphism. Two structures can be elementarily equivalent without being isomorphic (they can even have different cardinalities!). But if there exists an elementary embedding from $\mathcal{M}$ to $\mathcal{N}$, then certainly $\mathcal{M} \equiv \mathcal{N}$. Consistency: When Sentences Have Models For a set of sentences to be mathematically useful, we need to know that they don't contradict each other. This is where consistency comes in. A set of sentences $\Sigma$ is consistent if there exists at least one structure that satisfies every sentence in $\Sigma$. In other words, $\Sigma$ is consistent if $\Sigma$ has a model. A set of sentences is inconsistent if no structure can satisfy all of them—the sentences contradict each other. For example, $\{\forall x \, (x > 0), \exists x \, (x \leq 0)\}$ is inconsistent: no structure can make all objects positive and also have some non-positive object. Local consistency is a key concept: We say $\Sigma$ is locally consistent if every finite subset of $\Sigma$ has a model. In other words, no finite piece of $\Sigma$ contradicts itself, even if $\Sigma$ as a whole might be inconsistent. The relationship between consistency and local consistency is subtle and profound—and is the focus of the Compactness Theorem, our first major theorem. The Compactness Theorem Compactness Theorem: If every finite subset of a set of sentences $\Sigma$ has a model, then $\Sigma$ itself has a model. In other words: Local consistency implies full consistency. This is a remarkable result. It says that if no finite piece of your axioms contradicts itself, then there exists a structure (which might be infinite or even larger than your expectation) that satisfies all of them at once. Why is this called "compactness"? The name comes from topology. We can think of the space of all possible structures as a topological space, and the Compactness Theorem is equivalent to saying that certain subsets of this space are compact. But the intuitive meaning is clearer: the truth value of an infinite set of sentences is determined by the truth values of all its finite subsets—infinite behaviors can be "compressed" into finite properties. A simple example of Compactness: Suppose we want to construct a group where there exists an element of order larger than any finite number we specify. We can use Compactness: Let $\Sigma$ consist of the group axioms, plus sentences like "$\exists x \, (x^{1000000...000} \neq e)$" (the element $x$ raised to any huge power is not the identity) Every finite subset of $\Sigma$ is consistent: we can construct a finite group with an element of large enough order to satisfy all the finiteness requirements By Compactness, all of $\Sigma$ together has a model: a group with an element of infinite order Key insight: Compactness lets us build exotic infinite structures by ensuring that each finite piece of our requirements is satisfiable. This is a powerful technique used throughout model theory. The Completeness Theorem Completeness Theorem (Gödel, 1930): Let $T$ be a theory and $\varphi$ a sentence in the same language. Then $\varphi$ is true in all models of $T$ if and only if $\varphi$ can be proved from the axioms of $T$. In symbols: $$T \models \varphi \iff T \vdash \varphi$$ where $T \models \varphi$ means "$\varphi$ is true in all models of $T$" (semantic consequence) and $T \vdash \varphi$ means "$\varphi$ can be proved from $T$" (syntactic consequence). What does this mean? The Completeness Theorem says that the semantic notion of truth (what's true in all structures) coincides perfectly with the syntactic notion of provability (what can be derived from axioms). There is no gap between what's logically true and what we can prove—they're the same. This is profound because: It tells us that logical proof systems are complete: if something is true in all models, we can prove it It connects the formal, symbolic world of proofs with the concrete world of mathematical structures It justifies the use of formal reasoning: anything we can derive syntactically corresponds to a genuine semantic fact <extrainfo> Advanced note: The Completeness Theorem applies specifically to first-order logic. There are stronger logical systems (like second-order logic) that are more expressive but for which no complete proof system exists. This is one reason why first-order logic is so central to model theory. </extrainfo> Why These Theorems Matter Together The Compactness Theorem and Completeness Theorem are the two pillars of model theory: Compactness tells us that we can build interesting infinite structures by ensuring their finite pieces satisfy our requirements Completeness tells us that semantic truth and syntactic provability are the same thing Together, they create a powerful feedback loop: we can shift freely between thinking about structures and thinking about proofs, knowing that what's true semantically can be captured syntactically, and that locally consistent theories have models. <extrainfo> Applications and Extensions Application of Compactness: Model theorists use Compactness to prove existence theorems. For instance, they can prove that certain mathematical objects (like non-Archimedean fields, or non-standard models of arithmetic) must exist, even if no one can explicitly construct them. The technique is: set up the requirements using sentences, verify that every finite piece is satisfiable, then invoke Compactness to guarantee a model exists. Application of Completeness: In computer science and mathematical logic, Completeness ensures that automated theorem provers can find proofs of all valid statements. If something is true in all models of our axioms, a complete proof system will eventually find a derivation. Model-Theoretic Methods in Other Areas: These core theorems and concepts extend far beyond logic itself. In algebra, geometric model theory studies algebraic varieties through their first-order properties. In combinatorics, model-theoretic techniques are used to prove existence of infinite combinatorial structures. In analysis, non-standard analysis uses elementary equivalence to justify reasoning about infinitesimals. </extrainfo> Putting It All Together: The Model-Theoretic Perspective Model theory studies the correspondence between: Formal languages (syntax): abstract symbols and inference rules Mathematical structures (semantics): concrete domains with interpretations This correspondence is bidirectional. We can: Start with a mathematical structure and ask what properties it has (semantic → syntactic) Start with a collection of axioms and ask what structures satisfy them (syntactic → semantic) By translating back and forth between these perspectives, we gain new insights into both logical systems and mathematical structures. The key theoretical results—Compactness and Completeness—guarantee that this translation is faithful and powerful. Every semantic truth corresponds to a syntactic proof, and every locally consistent set of axioms has a model. This framework, developed largely in the 20th century, has become one of the most important tools in mathematical logic and has applications throughout mathematics.