Der Satz von Löb ist ein Ergebnis der mathematischen Logik, das von Martin Löb 1955 bewiesen wurde. Er besagt, dass in einer Theorie T, die bestimmte einfache Eigenschaften erfüllt und die Beweisbarkeit in T repräsentieren kann, für jede Formel P die Aussage „wenn P beweisbar ist, dann P“ nur dann beweisbar ist, wenn P beweisbar ist. Formal:
wenn , dann
wobei bedeutet, dass die Formel P in T beweisbar ist. (#P ist der der Gödelnummer von P zugeordnete Term.) Die Voraussetzungen des Satzes sind in allen hinreichend mächtigen mathematischen Theorien wie der Peano-Arithmetik und der Zermelo-Fraenkel-Mengenlehre erfüllt. Der Satz spielt eine wichtige Rolle in der Beweisbarkeitslogik.
Beweis Voraussetzungen Anstatt Beweisbarkeit in einer bestimmten Theorie zu betrachten, lässt sich der Satz von Löb ausgehend von wenigen abstrakten Eigenschaften von Beweisbarkeit zeigen. Ein Prädikat B heißt Beweisbarkeitsprädikat für eine Theorie T, wenn es für alle Formeln folgende drei Bedingungen erfüllt: Wenn , dann
Es lässt sich zeigen, dass eine Standard-Repräsentation der Beweisbarkeit in einer Theorie wie der Peano-Arithmetik oder der Mengenlehre diese drei Anforderungen erfüllt und somit ein Beweisbarkeitsprädikat ist.
Sei nun T eine Theorie, die folgende Eigenschaften hat: T besitzt ein Beweisbarkeitsprädikat B. Diagonalisierung: In T hat jede Formel mit freier Variable einen Fixpunkt im folgenden Sinne: Ist eine Formel mit freier Variable x, dann gibt es eine Formel , sodass gilt: , das heißt, hat die intuitive Bedeutung „Ich habe die Eigenschaft .“
Beweis Mit den angegebenen Voraussetzungen lässt sich der Satz von Löb wie folgt beweisen:Boolos et al. 2002, Seite 236–237
Sei eine Formel mit Durch Diagonalisierung erhält man aus der Formel eine Formel mit Wegen Axiom 1 ist Wegen Axiom 2 ist Aus 3 und 4 folgt: Wegen 2 und Axiom 2 ist: Aus 5 und 6 folgt: Wegen Axiom 3 gilt: Aus 7 und 8 folgt: Aus 1 und 9 folgt: Aus 2 und 10 folgt: Wegen Axiom 1 ist: Aus 10 und 12 folgt nun:
Anwendungen Ein Henkinsatz ist ein Satz, der seine eigene Beweisbarkeit ausdrückt. Der Satz von Löb zeigt, dass jeder Henkinsatz (insofern beweisbar ist, dass er ein solcher ist) beweisbar ist. Denn wenn ein Henkinsatz ist, gilt , also nach dem Satz von Löb .Boolos et al. 2002, Seite 235 P ist ein Wahrheitsprädikat, wenn für alle Formeln gilt: . Es lässt sich leicht zeigen, dass P auch ein Beweisbarkeitsprädikat für T ist. Nach dem Satz von Löb gilt dann für alle Formeln : und T ist inkonsistent. Also besitzt keine konsistente Theorie ein Wahrheitsprädikat.Boolos et al. 2002, Seite 237 Der zweite gödelsche Unvollständigkeitssatz besagt, dass ein hinreichend starkes und konsistentes formales System die eigene Konsistenz nicht beweisen kann. Dies lässt sich wie folgt aus dem Satz von Löb folgern. Angenommen beweist die eigene Konsistenz, d. h. . Dies ist äquivalent zu . Nach dem Satz von Löb ist somit und ist inkonsistent.
Literatur
Weblinks Satz von Löb bei PlanetMath The Cartoon Guide to Löb’s Theorem, von Eliezer Yudkowsky
Einzelnachweise
Lob Kategorie:Mathematische Logik