Advanced undergraduateFoundationsLesson available

Completeness, compactness and Löwenheim–Skolem

Gödel's completeness theorem and its consequences: compactness, the Löwenheim–Skolem theorems, nonstandard models and the limits of first-order axiomatisation.

math.found.completeness-theorem

Open lesson Show everything needed to reach this topic

Builds on

First-order logic Countability and Cantor's diagonal argument

Required prerequisites, all the way down: 16

You will learn to

Prove the completeness theorem for countable languages by a Henkin construction.
Use compactness to show that some classes, such as torsion groups or finite structures, are not first-order axiomatisable.
State the Löwenheim–Skolem theorems and explain Skolem's paradox.

Definition

A theory is consistent if it does not prove a contradiction, and satisfiable if it has a model.
Compactness: a set of sentences has a model whenever every finite subset of it has a model.

Theorem

Completeness: a first-order theory is consistent if and only if it has a model.
The compactness theorem holds for first-order logic.
Löwenheim–Skolem: a theory in a countable language with an infinite model has a model of every infinite cardinality.
Peano arithmetic has nonstandard models.

Common misconceptions

Thinking the completeness and incompleteness theorems contradict each other; one concerns truth in all models, the other provability of truths about one intended model.
Reading Skolem's paradox as an inconsistency: a countable model of ZFC contains no bijection between ω and its version of ℝ, although one exists outside the model.

Leads to

Model theory Gödel's incompleteness theorems Axiomatic set theory: hierarchy, cardinal arithmetic and L

Optional discoveries

Real analysis Compactness yields ordered fields elementarily equivalent to ℝ that contain infinitesimals, the basis of Robinson's nonstandard analysis.