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 $T\vdash (Bew_{T}(\#P)\rightarrow P)$, dann $T\vdash P$

wobei $Bew_{T}(\#P)$ 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 $\varphi ,\psi$ folgende drei Bedingungen erfüllt:

1. Wenn $T\vdash \varphi$, dann $T\vdash B(\#\varphi )$
2. $T\vdash B(\#(\varphi \rightarrow \psi ))\rightarrow (B(\#\varphi )\rightarrow B(\#\psi ))$
3. $T\vdash B(\#\varphi )\rightarrow B(\#B(\#\varphi ))$

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 $\varphi (x)$ eine Formel mit freier Variable x, dann gibt es eine Formel $\psi$, sodass gilt: $T\vdash \psi \leftrightarrow \varphi (\#\psi )$, das heißt, $\psi$ hat die intuitive Bedeutung „Ich habe die Eigenschaft $\varphi (x)$.“

Beweis

Mit den angegebenen Voraussetzungen lässt sich der Satz von Löb wie folgt beweisen:

1. Sei $\varphi$ eine Formel mit $T\vdash B(\#\varphi )\rightarrow \varphi$
2. Durch Diagonalisierung erhält man aus der Formel $(B(x)\rightarrow \varphi )$ eine Formel $\psi$ mit $T\vdash \psi \leftrightarrow (B(\#\psi )\rightarrow \varphi )$
3. Wegen Axiom 1 ist $T\vdash B(\#(\psi \rightarrow (B(\#\psi )\rightarrow \varphi )))$
4. Wegen Axiom 2 ist $T\vdash B(\#(\psi \rightarrow (B(\#\psi )\rightarrow \varphi )))\rightarrow (B(\#\psi )\rightarrow B(\#B(\#\psi )\rightarrow \varphi ))$
5. Aus 3 und 4 folgt: $T\vdash B(\#\psi )\rightarrow B(\#(B(\#\psi )\rightarrow \varphi )))$
6. Wegen 2 und Axiom 2 ist: $T\vdash B(\#(B(\#\psi )\rightarrow \varphi ))\rightarrow (B(\#B(\#\psi ))\rightarrow B(\#\varphi ))$
7. Aus 5 und 6 folgt: $T\vdash B(\#\psi )\rightarrow (B(\#B(\#\psi ))\rightarrow B(\#\varphi ))$
8. Wegen Axiom 3 gilt: $T\vdash B(\#\psi )\rightarrow B(\#B(\#\psi ))$
9. Aus 7 und 8 folgt: $T\vdash B(\#\psi )\rightarrow B(\#\varphi )$
10. Aus 1 und 9 folgt: $T\vdash B(\#\psi )\rightarrow \varphi$
11. Aus 2 und 10 folgt: $T\vdash \psi$
12. Wegen Axiom 1 ist: $T\vdash B(\#\psi )$
13. Aus 10 und 12 folgt nun: $T\vdash \varphi$

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 $\varphi$ ein Henkinsatz ist, gilt $T\vdash \varphi \leftrightarrow Bew_{T}(\#\varphi )$, also nach dem Satz von Löb $T\vdash \varphi$.
• P ist ein Wahrheitsprädikat, wenn für alle Formeln $\varphi$ gilt: $T\vdash P(\#\varphi )\leftrightarrow \varphi$. 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 $\varphi$: $T\vdash \varphi$ 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 $T$ beweist die eigene Konsistenz, d. h. $T\vdash \neg Bew_{T}(\#\bot )$. Dies ist äquivalent zu $T\vdash (Bew(\#\bot )\rightarrow \bot )$. Nach dem Satz von Löb ist somit $T\vdash \bot$ und $T$ ist inkonsistent.

Literatur

• George Boolos, John P. Burgess und Richard Jeffrey: Computability and Logic. 4. Auflage. Cambridge University Press, 2002, ISBN 0-521-70146-5. 
• Martin Hugo Löb: Solution of a Problem of Leon Henkin. In: Journal of Symbolic Logic. Band 20, 1955, S. 115–118. 

Weblinks

• Satz von Löb bei PlanetMath
• The Cartoon Guide to Löb’s Theorem, von Eliezer Yudkowsky