Universidad avanzadaFoundationsPlanificado
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
La lección de este tema todavía no se ha escrito. El esquema siguiente forma parte del mapa del plan de estudios y no ha sido revisado.
Se basa en
Requisitos previos obligatorios, hasta el fondo: 16
Aprenderás a
- 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.
Definición
- 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.
Teorema
- 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.
Errores frecuentes
- 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.
Conduce a
Descubrimientos opcionales
- Real analysis Compactness yields ordered fields elementarily equivalent to ℝ that contain infinitesimals, the basis of Robinson's nonstandard analysis.
Lecturas complementarias
- Herbert B. Enderton, A Mathematical Introduction to Logic (1972)
- David Marker, Model Theory: An Introduction (2002)