Kompaktheits- und Löwenheim-Skolem-Theoreme

Die Kompaktheits- und Löwenheim-Skolem-Theoreme sind die beiden grundlegenden Ergebnisse, die bestimmen, welche Strukturen erststufige Theorien beschreiben können, und offenbaren sowohl die Leistungsfähigkeit als auch die inhärenten Grenzen der Prädikatenlogik erster Stufe.

Definition

Das Kompaktheitstheorem besagt, dass eine Menge von erststufigen Sätzen genau dann erfüllbar ist, wenn jede endliche Teilmenge erfüllbar ist; die Löwenheim-Skolem-Theoreme besagen, dass jede erststufige Theorie mit einem unendlichen Modell Modelle in jeder unendlichen Kardinalität besitzt, die mindestens der Kardinalität ihrer Sprache entspricht.

Scope

Dieses Thema behandelt das Kompaktheitstheorem und seinen Beweis mittels Vollständigkeit oder Ultraprodukten, die absteigenden und aufsteigenden Löwenheim-Skolem-Theoreme über die Kardinalitäten von Modellen, ihre Standardkonsequenzen einschließlich der Existenz nicht-standardmäßiger Modelle der Arithmetik und Analysis sowie das Skolem-Paradoxon.

Core questions

• Warum garantiert die endliche Erfüllbarkeit einer Theorie ein Modell?
• Wie erzeugen diese Theoreme nicht-standardmäßige Modelle der Arithmetik und der reellen Zahlen?
• Warum kann keine erststufige Theorie eine unendliche Struktur bis auf Kardinalität charakterisieren?
• Was ist das Skolem-Paradoxon und wie wird es gelöst?

Key theories

Kompaktheitstheorem

Wenn jede endliche Teilmenge einer Satzmenge ein Modell hat, dann hat die gesamte Menge ein Modell; es folgt aus der Vollständigkeit oder kann semantisch mit Ultraprodukten bewiesen werden.

Absteigendes Löwenheim-Skolem-Theorem

Jede unendliche Struktur hat eine elementare Unterstruktur von Kardinalität höchstens der ihrer Sprache, sodass abzählbare Theorien mit unendlichen Modellen abzählbare Modelle haben.

Aufsteigendes Löwenheim-Skolem-Theorem

Jedes unendliche Modell kann elementar zu Modellen jeder größeren Kardinalität erweitert werden, sodass erststufige Theorien die Größe ihrer unendlichen Modelle nicht festlegen können.

Clinical relevance

Diese Theoreme sind die Arbeitspferde der Modelltheorie: Kompaktheit wird verwendet, um nicht-standardmäßige Modelle zu konstruieren, die Ergebnisse beweisen oder übertragen, und die Löwenheim-Skolem-Theoreme erklären, warum erststufige Axiomatisierungen der natürlichen Zahlen oder der reellen Zahlen immer unbeabsichtigte Modelle zulassen, was die Wahl logischer Rahmenwerke prägt.

History

Löwenheim bewies 1915 eine Version des absteigenden Theorems, und Skolem verallgemeinerte und präzisierte es in den 1920er Jahren. Die Kompaktheit wurde von Gödel als Korollar der Vollständigkeit erhalten und von Maltsev auf unzählbare Sprachen erweitert, der sie erstmals zur Ableitung algebraischer Theoreme nutzte und damit den Weg zur angewandten Modelltheorie ebnete.

Key figures

• Leopold Loewenheim
• Thoralf Skolem
• Kurt Goedel
• Anatoly Maltsev

Seminal works

• changkeisler1990
• marker2002
• hodges1993

Frequently asked questions

Was ist ein nicht-standardmäßiges Modell der Arithmetik?

Durch Kompaktheit kann man den Axiomen der Arithmetik eine Konstante hinzufügen, die größer ist als jede Ziffer; die resultierende konsistente Theorie hat ein Modell, das unendliche Elemente jenseits der Standard-Naturzahlen enthält. Solche Modelle erfüllen genau dieselben erststufigen Sätze wie das Standardmodell.

Was ist das Skolem-Paradoxon?

Das absteigende Löwenheim-Skolem-Theorem liefert ein abzählbares Modell der Mengenlehre, obwohl diese Theorie beweist, dass überabzählbare Mengen existieren. Die Auflösung besteht darin, dass die Überabzählbarkeit relativ zum Modell ist: Eine Menge, die das Modell als überabzählbar betrachtet, hat keine Bijektion mit den natürlichen Zahlen innerhalb des Modells, obwohl eine extern existiert.