跳到正文
The Lumenary
本科高年级Foundations计划中

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

显示到达此主题所需的全部内容

本主题的课程尚未编写。下面的提纲是课程地图的一部分，尚未经过审校。

前置知识

First-order logicCountability and Cantor's diagonal argument

16 项必需的前置知识（一直追溯到底）

你将学会

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

定义

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

定理

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

常见误解

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

通向

Model theoryGödel's incompleteness theoremsAxiomatic set theory: hierarchy, cardinal arithmetic and L

可选发现

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

延伸阅读

  • Herbert B. Enderton, A Mathematical Introduction to Logic (1972)
  • David Marker, Model Theory: An Introduction (2002)