المرحلة الجامعية المتقدمة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
لم يُكتب درس هذا الموضوع بعد. المخطط أدناه جزء من خريطة المنهج ولم تجرِ مراجعته.
يعتمد على
عدد المتطلبات السابقة الإلزامية (حتى الأساس): 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.
يقود إلى
اكتشافات اختيارية
- 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)