Satz von Löb
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:

 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 .
 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.
 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
Mathematische Logik