Prädikatenlogik erster Stufe und Vollständigkeit

Die Prädikatenlogik erster Stufe ist die formale Sprache quantifizierter Aussagen über Objekte und Relationen, und Gödels Vollständigkeitssatz zeigt, dass ihr Beweissystem genau die Sätze erfasst, die in allen Interpretationen wahr sind.

Definition

Die Prädikatenlogik erster Stufe erweitert die Aussagenlogik um Quantoren, die über einen Objektbereich zusammen mit Relations-, Funktions- und Konstantensymbolen reichen; der Vollständigkeitssatz besagt, dass ein Satz in seinem Beweissystem genau dann ableitbar ist, wenn er eine logische Konsequenz der angenommenen Axiome ist.

Scope

Dieses Thema behandelt die Syntax von Sprachen erster Stufe, Terme, Formeln und Sätze, die Semantik von Strukturen und Erfüllbarkeit, die Begriffe der Gültigkeit und logischen Konsequenz, ein deduktives System für die Prädikatenlogik erster Stufe sowie die Korrektheits- und Vollständigkeitssätze, die die Beweisbarkeit mit der Wahrheit in Beziehung setzen.

Core questions

• Was ist die präzise Syntax und Semantik der Prädikatenlogik erster Stufe?
• Was bedeutet es, dass ein Satz eine logische Konsequenz einer Theorie ist?
• Warum ist jeder gültige Satz formal beweisbar?
• Wie verbindet die Vollständigkeit das Beweissystem mit der Klasse aller Modelle?

Key theories

Korrektheitssatz

Jeder im Beweissystem ableitbare Satz ist in jedem Modell der Prämissen wahr, sodass das deduktive System niemals falsche Konsequenzen beweist.

Gödelscher Vollständigkeitssatz

Umgekehrt ist jeder Satz, der in allen Modellen einer Theorie gilt, aus dieser ableitbar, sodass Beweisbarkeit und logische Konsequenz für die Prädikatenlogik erster Stufe zusammenfallen.

Henkin-Konstruktion

Die Vollständigkeit wird bewiesen, indem ein Modell direkt aus einer maximal konsistenten Menge von Sätzen mit Zeugen für existentielle Aussagen konstruiert wird, was ein syntaktisches Rezept zur Konstruktion von Modellen liefert.

Clinical relevance

Die Prädikatenlogik erster Stufe ist der Standardrahmen zur Formalisierung mathematischer Theorien, und die Vollständigkeit garantiert, dass jede semantische Wahrheit, die allen Modellen gemeinsam ist, prinzipiell bewiesen werden kann, was das automatisierte Theorembeweisen und die fundamentale Angemessenheit axiomatischer Systeme untermauert.

History

Die Prädikatenlogik erster Stufe entstand aus Freges Begriffsschrift und wurde von Hilbert und Ackermann als eigenständiges System isoliert. Gödel bewies die Vollständigkeit in seiner Doktorarbeit von 1929, und Henkins Konstruktion von 1949 lieferte den vereinfachten Beweis unter Verwendung maximal konsistenter Mengen, der heute Standard ist.

Key figures

• Gottlob Frege
• Kurt Goedel
• Leon Henkin
• Alfred Tarski

Seminal works

• enderton2001
• marker2002
• shoenfield1967

Frequently asked questions

Wie unterscheidet sich die Vollständigkeit von Gödels Unvollständigkeitssätzen?

Vollständigkeit bezieht sich auf die logische Konsequenz: Jeder Satz, der in allen Modellen einer Theorie wahr ist, ist beweisbar. Unvollständigkeit bezieht sich auf eine spezifische Theorie: Eine hinreichend starke konsistente Theorie enthält Sätze, die in ihrem intendierten Modell wahr sind, die sie jedoch nicht beweisen kann. Die beiden betreffen unterschiedliche Begriffe und stehen nicht im Widerspruch.

Warum ist die Prädikatenlogik erster Stufe die Standardwahl?

Sie ist ausdrucksstark genug, um den größten Teil der Mathematik zu formalisieren, und genießt dennoch Vollständigkeit und Kompaktheit, die bei stärkeren Logiken wie der Prädikatenlogik zweiter Stufe fehlen. Dieses Gleichgewicht zwischen Ausdruckskraft und guten metatheoretischen Eigenschaften macht sie zum Standard-Logikrahmen.