Satz von Löb

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

Voraussetzungen[Bearbeiten]

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[Bearbeiten]

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

  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[Bearbeiten]

  • Ein Henkinsatz ist ein Satz, der seine eigene Beweisbarkeit ausdrückt. Der Satz von Löb zeigt, dass jeder Henkinsatz 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.[2]
  • 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.[3]
  • 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[Bearbeiten]

  •  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. 20, 1955, S. 115–118.

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Boolos et al. 2002, Seite 236-237
  2. Boolos et al. 2002, Seite 235
  3. Boolos et al. 2002, Seite 237