Model Theory Introduction

⚡ Key Takeaways

Model theory studies mathematical structures (models) through the lens of formal logical languages, analyzing what classes of structures can be defined and how syntactic descriptions (theories) relate to semantic objects (models). Its central engine is the interplay between satisfaction and provability, crystallized in the Compactness and Löwenheim–Skolem theorems. It applies anywhere structures are axiomatized — algebra (fields, groups), arithmetic, combinatorics, and even analysis. Founded by Löwenheim, Skolem, Gödel, Tarski, and Robinson in the 1915–1960 era.

💡 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.

DefinitionLanguage (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 \geq 1$ ,
Relation (predicate) symbols $R, S, \dots$ , each with an arity $n \geq 1$ ,

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

DefinitionStructure

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}}\})$ .

DefinitionSemantic Consequence and Theory of a Structure

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

4

\quad \operatorname{Th}(\mathcal{M}) = \{\varphi : \varphi \text{ is an } \mathcal{L}\text{-sentence and } \mathcal{M} \models \varphi\}.

Derivation hint: $\operatorname{Th}(\mathcal{M})$ is automatically <strong>complete</strong> — for every sentence $\varphi$ either $\varphi$ or $\neg\varphi$ lies in it — and <strong>consistent</strong>, since $\mathcal{M}$ is an explicit model.

TheoremCompactness 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 \varphi$ then $T_0 \models \varphi$ for some finite $T_0 \subseteq T$ .

TheoremLöwenheim–Skolem Theorems

(Downward) If an $\mathcal{L}$ -theory $T$ in a countable language has an infinite model, then it has a model of every infinite cardinality $\kappa \geq \aleph_0$ . More precisely, any infinite structure $\mathcal{M}$ has an elementary substructure of cardinality $\max(\aleph_0, |\mathcal{L}|)$ . (Upward) If $T$ has an infinite model, it has models of every cardinality $\kappa \geq \max(|\mathcal{L}|, \aleph_0)$ .

ProofCompactness via the Completeness Theorem

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

Step 1 — Finiteness of proofs. A formal proof in a Hilbert (or natural-deduction) calculus is a finite sequence of formulas. Hence if $T \vdash \varphi$ , only finitely many sentences of $T$ appear as premises; call this finite set $T_0$ . Thus $T_0 \vdash \varphi$ .

Step 2 — Contrapositive setup. Suppose every finite subset of $T$ has a model but $T$ has none. " $T$ has no model" means $T$ is unsatisfiable. By Completeness (specifically its consistency–satisfiability form), an unsatisfiable theory is inconsistent: $T \vdash \bot$ (a contradiction, e.g. $\psi \wedge \neg\psi$ ).

Step 3 — Localize the inconsistency. By Step 1, the derivation of $\bot$ uses only a finite subset $T_0 \subseteq T$ , so $T_0 \vdash \bot$ , i.e. $T_0$ is inconsistent and hence (by Completeness again) unsatisfiable.

Step 4 — Contradiction. But $T_0$ is a finite subset, which by hypothesis has a model. Contradiction. Therefore $T$ has a model. $\blacksquare$ 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$ .

∎

ProofUpward Löwenheim–Skolem via Compactness

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

Step 1. Expand the language by adding $\kappa$ many fresh distinct constant symbols $\{c_\alpha : \alpha < \kappa\}$ .

Step 2. Form the theory $T' = T \cup \{c_\alpha \neq c_\beta : \alpha < \beta < \kappa\}$ .

Step 3. Any finite subset $T'_0$ mentions only finitely many of the new constants, say $c_{\alpha_1}, \dots, c_{\alpha_n}$ . Since $\mathcal{M}$ is infinite, we can interpret these constants as $n$ distinct elements of $M$ , making $\mathcal{M}$ (so expanded) a model of $T'_0$ .

Step 4. By Compactness, $T'$ has a model $\mathcal{N}$ . Its $\kappa$ distinct constants force $|N| \geq \kappa$ . Reducing back to $\mathcal{L}$ and applying Downward Löwenheim–Skolem if needed gives a model of $T$ of cardinality exactly $\kappa$ . $\blacksquare$

∎

mathematician · Alfred Tarski | 1901–1983

Polish-American logician who gave the rigorous definition of truth in formalized languages (1933), turning the intuitive " $\mathcal{M}$ satisfies $\varphi$ " 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.

🧠 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 \neq 0, c \neq 1, c \neq 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.

Figure

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

ExampleNonstandard Models of Arithmetic

Given. Let $\mathcal{N} = (\mathbb{N}, +, \cdot, <, 0, 1)$ and let $T = \operatorname{Th}(\mathcal{N})$ be true arithmetic. We construct a model containing an "infinite" number.

Steps. 1. Add a fresh constant $c$ to the language $\mathcal{L}_{\text{arith}}$ . 2. Form $T' = T \cup \{\, c > \underbrace{1 + 1 + \cdots + 1}_{n} : n \in \mathbb{N}\,\}$ , i.e. $c > \bar n$ for every numeral $\bar n$ . 3. Finite satisfiability: any finite subset of $T'$ 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'$ has a model $\mathcal{M}^*$ . 5. In $\mathcal{M}^*$ , the element $c^{\mathcal{M}^*}$ exceeds every standard numeral $\bar n$ — it is a nonstandard (infinite) natural number. 6. Since $\mathcal{M}^* \models T = \operatorname{Th}(\mathcal{N})$ , it is elementarily equivalent to $\mathcal{N}$ : it satisfies exactly the same first-order sentences.

Boxed answer.

\boxed{\;\mathcal{M}^* \equiv \mathcal{N}, \quad \text{yet } \mathcal{M}^* \text{ contains } c^{\mathcal{M}^*} > \bar n \ \forall n \in \mathbb{N}.\;}

The existence of nonstandard models shows that no first-order theory can categorically describe $\mathbb{N}$ up to isomorphism.

ExampleCounting Models: Vector Spaces and Categoricity

Given. Let $K = \mathbb{Q}$ and consider the theory $T$ of infinite $\mathbb{Q}$ -vector spaces in the language $\mathcal{L} = \{+, 0\} \cup \{ \lambda_q : q \in \mathbb{Q}\}$ where $\lambda_q$ is a unary scalar-multiplication function. We count models up to isomorphism in each uncountable cardinality.

Steps. 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.

Boxed answer.

\boxed{\;I(T,\kappa) = 1 \text{ for } \kappa > \aleph_0, \qquad I(T,\aleph_0) = \aleph_0.\;}

This illustrates Morley's Categoricity Theorem: a countable theory categorical in one uncountable cardinal is categorical in all of them.

⚠️ Common mistake

" $\models$ and $\vdash$ are the same thing." They are defined completely differently — $\models$ is semantic (truth in all models), $\vdash$ is syntactic (existence of a formal proof). Their equivalence is the content of Gödel's Completeness Theorem and holds for first-order logic, but fails for second-order logic (which has no complete proof system). Conflating them erases the very distinction model theory exists to study.

⚠️ Common mistake

"Completeness Theorem and Incompleteness Theorem contradict each other." They do not. Completeness says $T \vdash \varphi \iff T \models \varphi$ — provability captures semantic consequence. Incompleteness says a specific theory (e.g. Peano Arithmetic) is not negation-complete: there is a sentence $\varphi$ with neither $\text{PA} \vdash \varphi$ nor $\text{PA} \vdash \neg\varphi$ . These are about different uses of the word "complete."

CounterexampleFirst-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 \neq 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.

connection

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.

🔬 Where this appears

⏳ History

- 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

\vdash \iff \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.

open-problem

Vaught's Conjecture (1961) asserts that a countable complete first-order theory has either at most $\aleph_0$ or exactly $2^{\aleph_0}$ countable models up to isomorphism — never an intermediate number. It remains open in general (proved for several large classes, e.g. $\omega$ -stable theories by Shelah–Harrington–Makkai, and for o-minimal theories). The conjecture probes whether the descriptive-set-theoretic complexity of the isomorphism relation can be "intermediate," tying model theory to descriptive set theory and the analysis of Borel equivalence relations. More broadly, Shelah's classification program seeks a complete dividing-line picture (stable / NIP / NSOP / simple) for all first-order theories; while stability and simplicity theory are mature, the geometry of NIP and the Main Gap above the countable have generated deep ongoing research, and the precise structure theory for unstable theories is far from settled.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also