Model Theory Introduction

Model theory is the branch of mathematical logic that examines the relationship between formal theories — sets of sentences in a first-order language — and their models, the mathematical structures in which those sentences are true. A structure interprets the symbols of a language as concrete objects, functions, and relations; a theory is satisfied by a structure when every sentence of the theory holds. The discipline matters because it converts hard structural questions into manageable syntactic ones and vice versa: one can prove the existence of objects (infinitesimals, algebraically closed extensions) by purely logical arguments. A surprising fact is the Löwenheim–Skolem phenomenon: any first-order theory with an infinite model has models of every infinite cardinality, so first-order logic cannot pin down the size of an infinite structure — leading to the famous Skolem "paradox" that countable models of set theory exist despite proving uncountable sets to exist.

The Core Insight

A first-order sentence is a finite syntactic object, yet it carves out a class of structures (its models) that can be enormous and varied. Model theory exploits a fundamental finiteness baked into first-order proof — only finitely many premises can be used in any single deduction — to obtain the Compactness Theorem: a set of sentences has a model iff every finite subset does. From compactness flow nearly all the foundational results, including the failure of first-order logic to control cardinality and the existence of nonstandard models of arithmetic and analysis.

Formal Statement

Language (Signature)

A first-order language (or signature) $\mathcal{L}$ is a collection of symbols partitioned into:

• Constant symbols $c_0,c_1,\dots$
• Function symbols $f,g,\dots$, each with an arity $n\ge 1$,
• Relation (predicate) symbols $R,S,\dots$, each with an arity $n\ge 1$,

together with the fixed logical symbols: variables $v_0,v_1,\dots$, connectives $\neg ,\wedge ,\vee ,\to$, quantifiers $\forall ,\exists$, equality $=$, and parentheses. The language of rings, for example, is ${\mathcal{L}}_{\text{ring}}=\{+,\cdot ,-,0,1\}$.

Structure

An $\mathcal{L}$-structure $\mathcal{M}$ consists of a nonempty set $M$ (the domain or universe) together with an interpretation assigning:

• to each constant symbol $c$ an element $c^{\mathcal{M}}\in M$,
• to each $n$-ary function symbol $f$ a function $f^{\mathcal{M}}:M^n\to M$,
• to each $n$-ary relation symbol $R$ a relation $R^{\mathcal{M}}\subseteq M^n$.

We write $\mathcal{M}=(M,\{c^{\mathcal{M}}\},\{f^{\mathcal{M}}\},\{R^{\mathcal{M}}\})$.

The notion of truth in a structure is defined recursively. Given an assignment $s$ mapping variables to elements of $M$, terms are evaluated, and satisfaction of a formula $\phi$ is written $\mathcal{M}\models \phi [s]$. The atomic clauses are:

The recursive clauses for connectives and quantifiers:

A sentence is a formula with no free variables; its truth does not depend on $s$, so we write $\mathcal{M}\models \phi$. A theory $T$ is a set of sentences; $\mathcal{M}\models T$ means $\mathcal{M}\models \phi$ for all $\phi \in T$, and $\mathcal{M}$ is then a model of $T$.

Semantic Consequence and Theory of a Structure

A sentence $\phi$ is a semantic consequence of $T$, written $T\models \phi$, if every model of $T$ satisfies $\phi$. The (complete) theory of a structure $\mathcal{M}$ is

Compactness Theorem

A set $T$ of first-order sentences has a model if and only if every finite subset of $T$ has a model. Equivalently, if $T\models \phi$ then $T_0\models \phi$ for some finite $T_0\subseteq T$.

Löwenheim–Skolem Theorems

Why It Holds / Derivation

Compactness via the Completeness Theorem

We sketch the standard route: Compactness follows from Gödel's Completeness Theorem ($T⊢\phi ⟺T\models \phi$), which equates syntactic provability with semantic consequence.

An alternative, purely semantic proof builds the model directly via ultraproducts: take an ultrafilter $\mathcal{U}$ on the index set of finite subsets and form ${\prod }_i{\mathcal{M}}_i/\mathcal{U}$; Łoś's theorem guarantees the resulting structure satisfies $T$.

Upward Löwenheim–Skolem via Compactness

Let $\mathcal{M}\models T$ be infinite and let $\kappa \ge \max (|\mathcal{L}|,{\aleph }_0)$.

Alfred Tarski | 1901–1983

Polish-American logician who gave the rigorous definition of truth in formalized languages (1933), turning the intuitive "$\mathcal{M}$ satisfies $\phi$" into the recursive clauses [1]–[3] that ground all of model theory. Tarski introduced the notions of elementary equivalence, definability, and quantifier elimination, proved the decidability of the theory of real closed fields and of Euclidean geometry, and (with his students at Berkeley) effectively created model theory as an autonomous discipline in the 1950s–60s. His work on the undefinability of truth complements Gödel's incompleteness and frames the entire syntax–semantics dialogue.

Building Intuition

Think of a theory as a list of constraints and a model as a concrete world satisfying them. First-order logic is "myopic": each axiom and each proof only ever sees finitely much information at once. Compactness is the precise statement of this myopia — you cannot rule out a model with a single global, infinitary condition; you can only rule it out via some finite local conflict. This explains why first-order logic cannot express "the domain is finite," "the domain is countable," or "every element is reachable from $0$ by finitely many successors" (well-foundedness / standardness). The moment you try, compactness conjures a model violating your intent — adding a constant $c$ "infinitely far out" with axioms $c\ne 0,c\ne 1,c\ne 1+1,\dots$, all finitely satisfiable, hence jointly satisfiable, giving a nonstandard element. Model theory is thus the study of what survives this myopia and what slips through it.

The syntax–semantics correspondence: theories on the left, their model classes on the right, linked by satisfaction and provability

Worked Examples

Nonstandard Models of Arithmetic

1. Add a fresh constant $c$ to the language ${\mathcal{L}}_{\text{arith}}$.
2. Form $T^{\prime }=T\cup \{c>\underset{n}{\underbrace{1+1+\cdots +1}}:n\in \mathbb{N}\}$, i.e. $c>\bar{n}$ for every numeral $\bar{n}$.
3. Finite satisfiability: any finite subset of $T^{\prime }$ contains $c>\bar{n}$ for finitely many $n$, with maximum $N$. Interpret $c:=N+1$ in $\mathcal{N}$; all those inequalities hold. So every finite subset has a model.
4. By Compactness, $T^{\prime }$ has a model ${\mathcal{M}}^{\ast }$.
5. In ${\mathcal{M}}^{\ast }$, the element $c^{{\mathcal{M}}^{\ast }}$ exceeds every standard numeral $\bar{n}$ — it is a nonstandard (infinite) natural number.
6. Since ${\mathcal{M}}^{\ast }\models T=\mathrm{Th}(\mathcal{N})$, it is elementarily equivalent to $\mathcal{N}$: it satisfies exactly the same first-order sentences.

Counting Models: Vector Spaces and Categoricity

1. A $\mathbb{Q}$-vector space is determined up to isomorphism by its dimension over $\mathbb{Q}$.
2. For a vector space of cardinality $\kappa >{\aleph }_0$, the cardinality equals $\max ({\aleph }_0,\dim )=\dim$, so $\dim =\kappa$.
3. Hence in each uncountable $\kappa$ there is, up to isomorphism, exactly one model: the space of dimension $\kappa$. The theory is $\kappa$-categorical for all uncountable $\kappa$.
4. In the countable case $\kappa ={\aleph }_0$, dimensions $1,2,3,\dots ,{\aleph }_0$ all give nonisomorphic countable models — countably many of them — so $T$ is not ${\aleph }_0$-categorical.

Common Misconceptions

First-order logic cannot express finiteness

Suppose, for contradiction, a single sentence ${\sigma }_{\text{fin}}$ held in $\mathcal{M}$ exactly when $|M|$ is finite. Consider $T=\{{\sigma }_{\text{fin}}\}\cup \{\exists x_1\cdots \exists x_n{\bigwedge }_{i<j}{x}_i\ne x_j:n\in \mathbb{N}\}$, where the $n$-th sentence says "there exist at least $n$ distinct elements." Every finite subset is satisfiable (take a large finite set). By Compactness, $T$ has a model $\mathcal{M}$, which is then both finite (by ${\sigma }_{\text{fin}}$) and infinite (by the at-least-$n$ axioms) — absurd. Hence no such ${\sigma }_{\text{fin}}$ exists; the class of finite structures is not first-order axiomatizable, though its complement (being infinite) is.

Connections

Model theory sits at the crossroads of logic and the rest of mathematics. It feeds on First-Order Logic for its syntax and on Set Theory for its cardinal arithmetic (Löwenheim–Skolem, categoricity). The ultraproduct construction links it to Ultrafilters and the Stone–Čech Compactification and provides Robinson's Nonstandard Analysis, a rigorous calculus of infinitesimals. Through quantifier elimination and model completeness it connects deeply to algebra: the theory of Algebraically Closed Fields and of Real Closed Fields yields the Tarski–Seidenberg theorem and o-minimality, the backbone of o-minimal Structures used in real algebraic geometry. Its stability theory (Shelah) interfaces with Combinatorics and recently with Arithmetic Geometry via the work on the Mordell–Lang and André–Oort conjectures.

Real-World Applications

1. Nonstandard analysis (Robinson, 1961): model theory legitimizes infinitesimals, giving streamlined proofs in calculus, measure theory, and probability (Loeb measures).
2. Algebraic geometry — Ax–Grothendieck theorem: every injective polynomial map ${\mathbb{C}}^n\to {\mathbb{C}}^n$ is surjective, proved via compactness by transfer from finite fields $\overline{{\mathbb{F}}_p}$.
3. Diophantine geometry: Hrushovski's model-theoretic proof of the Mordell–Lang conjecture for function fields, using stability and Zariski geometries.
4. Decision procedures: Tarski's quantifier elimination for real closed fields underlies cylindrical algebraic decomposition used in computer algebra systems (e.g. solving systems of polynomial inequalities, robot motion planning).
5. Database theory: first-order definability and finite model theory govern the expressive power of relational query languages (SQL ≈ first-order logic).
6. Verification & SMT solvers: the theory of arrays, of linear arithmetic, and of equality with uninterpreted functions are model-theoretically analyzed for decidability in hardware/software verification.
7. Combinatorics — regularity: stable and NIP theories yield strengthened Szemerédi regularity lemmas (Malliaris–Shelah) and bounds in extremal graph theory.

Historical Development

• 1915 — Leopold Löwenheim proves that a first-order sentence with an infinite model has a countable model — the first Löwenheim–Skolem result.
• 1920–1923 — Thoralf Skolem generalizes to theories and arbitrary cardinalities; identifies the Skolem paradox (countable models of set theory) and introduces Skolem functions.
• 1929–1930 — Kurt Gödel proves the Completeness Theorem for first-order logic in his doctoral thesis, establishing $⊢⟺\models$; Compactness follows.
• 1931 — Gödel proves the Incompleteness Theorems, sharply separating completeness from negation-completeness.
• 1933 — Alfred Tarski publishes "The Concept of Truth in Formalized Languages," giving the recursive definition of satisfaction.
• 1948–1951 — Tarski proves quantifier elimination and decidability for real closed fields and elementary geometry.
• 1955 — Jerzy Łoś proves the fundamental theorem of ultraproducts (Łoś's theorem), giving a semantic proof of compactness.
• 1961 — Abraham Robinson founds nonstandard analysis; develops model completeness and the model theory of fields.
• 1965 — Michael Morley proves the Categoricity Theorem, launching classification (stability) theory; Shelah (1970s–90s) erects the vast edifice of stability and classification theory.

Subtleties & Limits

See Also