Advanced undergraduateFoundationsPlanned

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

Show everything needed to reach this topic

The lesson for this topic has not been written yet. The outline below is part of the curriculum map and has not been reviewed.

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.