Foundations

Model Theory Basics

Model theory separates syntax (formulas, proofs) from semantics (structures, truth). Soundness: provable implies true. Completeness: true in all models implies provable. Compactness and Lowenheim-Skolem reveal that first-order logic cannot pin down infinite structures uniquely.

AdvancedTier 3Stable~50 min

Prerequisites

Basic Logic and Proof Techniques

Why This Matters

Model theory makes precise the distinction between what you can say and what is true. A formula is a syntactic object; a structure (model) is a mathematical object. A formula is true in a structure if the structure satisfies it. A formula is provable if it can be derived from axioms using inference rules.

These are different concepts, and understanding their relationship is the subject of model theory. The two central results are soundness (provable implies true in all models) and completeness (true in all models implies provable, for first-order logic). The compactness and Lowenheim-Skolem theorems reveal surprising limitations of first-order logic: you cannot use first-order sentences to uniquely characterize the natural numbers or to distinguish countable from uncountable structures.

This discipline trains a habit that matters throughout mathematics and ML: always distinguish the representation (your formula, your model class, your loss function) from the thing it represents (the underlying mathematical structure, the true data distribution).

Core Definitions

Definition

First-Order Language

A first-order language $\mathcal{L}$ consists of:

Constant symbols: $c_1, c_2, \ldots$ (names for specific elements)
Function symbols: $f_1, f_2, \ldots$ (each with a fixed arity)
Relation symbols: $R_1, R_2, \ldots$ (each with a fixed arity)
Logical symbols: $\land, \lor, \neg, \to, \forall, \exists, =$
Variables: $x_1, x_2, \ldots$

Formulas are built from atomic formulas ( $R(t_1, \ldots, t_n)$ and $t_1 = t_2$ ) using logical connectives and quantifiers.

Definition

Structure (Model)

An $\mathcal{L}$ -structure $\mathcal{M}$ consists of:

A nonempty set $M$ called the domain (or universe)
For each constant symbol $c$ , an element $c^\mathcal{M} \in M$
For each $n$ -ary function symbol $f$ , a function $f^\mathcal{M}: M^n \to M$
For each $n$ -ary relation symbol $R$ , a relation $R^\mathcal{M} \subseteq M^n$

A structure gives meaning to the symbols in the language.

Definition

Satisfaction

A structure $\mathcal{M}$ satisfies (or models) a sentence $\phi$ , written $\mathcal{M} \models \phi$ , if $\phi$ is true when interpreted in $\mathcal{M}$ . The definition is recursive:

$\mathcal{M} \models R(a_1, \ldots, a_n)$ iff $(a_1, \ldots, a_n) \in R^\mathcal{M}$
$\mathcal{M} \models \phi \land \psi$ iff $\mathcal{M} \models \phi$ and $\mathcal{M} \models \psi$
$\mathcal{M} \models \forall x.\, \phi(x)$ iff for every $a \in M$ , $\mathcal{M} \models \phi(a)$
And so on for other connectives and quantifiers.

Definition

Theory

A theory $T$ is a set of sentences. A structure $\mathcal{M}$ is a model of $T$ if $\mathcal{M} \models \phi$ for every $\phi \in T$ . A sentence $\phi$ is a logical consequence of $T$ , written $T \models \phi$ , if every model of $T$ satisfies $\phi$ .

Definition

Soundness and Completeness

A proof system is sound if every provable sentence is true in all models: $T \vdash \phi$ implies $T \models \phi$ . A proof system is complete if every sentence true in all models is provable: $T \models \phi$ implies $T \vdash \phi$ .

Main Theorems

Theorem

Godel's Completeness Theorem

Statement

For any first-order theory $T$ and sentence $\phi$ :

$T \models \phi \iff T \vdash \phi$

A first-order sentence is provable from $T$ if and only if it is true in every model of $T$ . Equivalently: a theory $T$ has a model if and only if it is consistent (no contradiction is derivable from $T$ ).

Intuition

The proof system for first-order logic is strong enough to derive every semantic consequence. Nothing is "lost" by working syntactically instead of semantically. If a sentence is true in every possible interpretation of the axioms, then there is a finite proof of it.

Proof Sketch

Soundness ( $\vdash$ implies $\models$ ) is a routine induction on proof length: verify that each axiom is valid in every structure and that each inference rule preserves truth under every interpretation.

Completeness ( $\models$ implies $\vdash$ ) is the hard direction. The standard proof (Henkin's method): given a consistent theory $T$ , extend it to a maximally consistent theory $T^*$ (using Zorn's lemma or a direct construction). Add "Henkin witnesses": for each existential sentence $\exists x.\, \phi(x)$ , add a new constant $c$ and the sentence $\phi(c)$ . The resulting theory $T^*$ describes a structure directly: the domain is the set of constant terms, and the interpretation is read off from $T^*$ .

Why It Matters

Completeness justifies the syntactic approach to logic. You do not need to reason about all possible structures (infinitely many, of all sizes). You can instead search for a finite proof. This is the theoretical foundation of automated theorem proving: proof search is complete for first-order logic.

Note: this completeness theorem is distinct from Godel's incompleteness theorems. The completeness theorem says first-order logic is complete as a proof system. The incompleteness theorems say specific first-order theories (like arithmetic) are incomplete: they have true sentences that are not provable within the theory.

Failure Mode

Completeness fails for second-order logic: there are second-order validities that have no proof in any recursively enumerable proof system. Completeness also fails for logics with generalized quantifiers or fixed-point operators. First-order logic occupies a sweet spot: expressive enough to be useful, but weak enough that a complete proof system exists.

Theorem

Compactness Theorem

Statement

A set of first-order sentences $T$ has a model if and only if every finite subset of $T$ has a model.

Equivalently: if $T \models \phi$ , then there is a finite subset $T_0 \subseteq T$ such that $T_0 \models \phi$ .

Intuition

Inconsistency is a finite phenomenon. If a theory is contradictory, the contradiction can be derived from finitely many axioms. You cannot create an inconsistency that requires infinitely many axioms simultaneously.

Proof Sketch

From the completeness theorem: $T$ is consistent iff $T$ has a model. If every finite subset of $T$ is consistent (has a model), then $T$ itself is consistent (because a proof of contradiction would use only finitely many axioms, contradicting the assumption). So $T$ has a model.

Why It Matters

Compactness has striking consequences. It implies that first-order logic cannot express "the domain is finite" or "the domain is countable." Any first-order theory with arbitrarily large finite models has an infinite model (add constants $c_1, c_2, \ldots$ with axioms $c_i \neq c_j$ for all $i \neq j$ ; every finite subset is satisfiable, so by compactness the whole set is). This is a fundamental limitation of first-order expressiveness.

Failure Mode

Compactness fails for many extensions of first-order logic. It fails for second-order logic, for first-order logic with the quantifier "there exist infinitely many," and for logics with fixed-point operators. The compactness theorem is closely tied to first-order logic specifically.

Lowenheim-Skolem Theorem

Theorem

Lowenheim-Skolem Theorem

Statement

Downward: if a first-order theory $T$ in a countable language has an infinite model, then it has a countable model.

Upward: if $T$ has an infinite model of cardinality $\kappa$ , then for every $\lambda \geq \kappa$ , $T$ has a model of cardinality $\lambda$ .

Intuition

First-order logic cannot control the size of its models. If a theory has any infinite model, it has models of every infinite cardinality. This means you cannot write a first-order theory whose only model is $\mathbb{R}$ (uncountable): any such theory also has countable models ("Skolem's paradox").

Proof Sketch

Downward: given a model $\mathcal{M}$ , start with any countable subset $A_0 \subseteq M$ . Close under all functions and Skolem functions (witnesses for existential statements). The resulting countable set $A = \bigcup_n A_n$ forms the domain of a countable elementary submodel.

Upward: use compactness. Add $\lambda$ many new constant symbols $\{c_\alpha : \alpha < \lambda\}$ with axioms $c_\alpha \neq c_\beta$ for $\alpha \neq \beta$ . Every finite subset of these axioms is satisfiable (in the given infinite model), so by compactness, the whole set is satisfiable. The model has cardinality at least $\lambda$ .

Why It Matters

Lowenheim-Skolem combined with compactness shows that first-order logic has a limited ability to distinguish structures. This is a feature, not a bug: it is precisely this limitation that makes first-order logic amenable to complete proof systems and decidable fragments.

Failure Mode

The theorem does not apply to second-order logic. In second-order logic, you can characterize $\mathbb{N}$ uniquely (up to isomorphism) using the second-order induction axiom. But second-order logic loses completeness and compactness.

Syntax vs. Semantics: The Core Discipline

Model theory trains a specific mental habit: always distinguish what you wrote from what it means.

Syntactic side	Semantic side
Formula $\phi$	Truth value of $\phi$ in $\mathcal{M}$
Theory $T$ (set of axioms)	Class of models satisfying $T$
Proof of $\phi$ from $T$	$\phi$ true in every model of $T$
Consistency of $T$	$T$ has at least one model

In ML, this distinction appears as: the loss function (syntax) vs. the generalization behavior (semantics), the hypothesis class (syntax) vs. the realizable functions (semantics), the training objective (what you optimize) vs. the actual risk (what you want to minimize).

Common Confusions

Watch Out

Completeness theorem is not the incompleteness theorem

Godel proved both, and the names are confusing. The completeness theorem says first-order logic (as a proof system) is complete: everything true in all models is provable. The incompleteness theorems say specific theories (like Peano Arithmetic) are incomplete: there exist sentences true in the standard model that are not provable from the axioms. These are compatible: the unprovable sentence of PA is true in $\mathbb{N}$ but not in all models of PA (there are nonstandard models where it is false).

Watch Out

Skolem's paradox is not a real paradox

ZFC proves uncountable sets exist, yet Lowenheim-Skolem says ZFC has a countable model. This is not a contradiction. Inside the countable model, the set that "is uncountable" has no bijection with $\mathbb{N}$ as seen from within the model. But from outside, the entire model is countable. The notion of uncountability is relative to the model. This illustrates that first-order logic cannot capture absolute cardinality.

Exercises

ExerciseCore

Problem

Give an example of a set of first-order sentences that is finitely satisfiable (every finite subset has a model) but whose only models are infinite. Explain why this does not contradict compactness.

ExerciseAdvanced

Problem

Explain why there is no first-order sentence (or set of sentences) whose models are exactly the finite structures. Use compactness.

ExerciseAdvanced

Problem

State precisely the difference between Godel's completeness theorem and Godel's first incompleteness theorem. Are they contradictory?

References

Canonical:

Enderton, A Mathematical Introduction to Logic (2001), Chapters 2-3
Marker, Model Theory: An Introduction (2002), Chapters 1-2
Chang & Keisler, Model Theory (3rd ed., 1990)

Accessible:

Hodges, A Shorter Model Theory (1997)
Munkres, Topology (2000), Chapter 1 (set theory review)

Next Topics

Proof theory and cut-elimination: the syntactic side of logic, complementary to model theory
SAT/SMT and automated reasoning: where these metatheorems become practical

Last reviewed: April 2026

Prerequisites

Foundations this topic depends on.

Basic Logic and Proof TechniquesLayer 0A