www.wikidata.de-de.nina.az

Satz von Löb Der ist ein Ergebnis der mathematischen Logik das von Martin Löb 1955 bewiesen wurde Er besagt dass in eine

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:

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 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 folgende drei Bedingungen erfüllt:

  1. 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 Bearbeiten

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

  1. Sei eine Formel mit
  2. Durch Diagonalisierung erhält man aus der Formel eine Formel mit
  3. Wegen Axiom 1 ist
  4. Wegen Axiom 2 ist
  5. Aus 3 und 4 folgt:
  6. Wegen 2 und Axiom 2 ist:
  7. Aus 5 und 6 folgt:
  8. Wegen Axiom 3 gilt:
  9. Aus 7 und 8 folgt:
  10. Aus 1 und 9 folgt:
  11. Aus 2 und 10 folgt:
  12. Wegen Axiom 1 ist:
  13. Aus 10 und 12 folgt nun:

Anwendungen Bearbeiten

  • 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 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. Band 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
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der Satz von Lob ist ein Ergebnis der mathematischen Logik das von Martin Lob 1955 bewiesen wurde Er besagt dass in einer Theorie T die bestimmte einfache Eigenschaften erfullt und die Beweisbarkeit in T reprasentieren kann fur jede Formel P die Aussage wenn P beweisbar ist dann P nur dann beweisbar ist wenn P beweisbar ist Formal wenn T B e w T P P displaystyle T vdash Bew T P rightarrow P dann T P displaystyle T vdash P wobei B e w T P displaystyle Bew T P bedeutet dass die Formel P in T beweisbar ist P ist der der Godelnummer von P zugeordnete Term Die Voraussetzungen des Satzes sind in allen hinreichend machtigen mathematischen Theorien wie der Peano Arithmetik und der Zermelo Fraenkel Mengenlehre erfullt Der Satz spielt eine wichtige Rolle in der Beweisbarkeitslogik Inhaltsverzeichnis 1 Beweis 1 1 Voraussetzungen 1 2 Beweis 2 Anwendungen 3 Literatur 4 Weblinks 5 EinzelnachweiseBeweis BearbeitenVoraussetzungen Bearbeiten Anstatt Beweisbarkeit in einer bestimmten Theorie zu betrachten lasst sich der Satz von Lob ausgehend von wenigen abstrakten Eigenschaften von Beweisbarkeit zeigen Ein Pradikat B heisst Beweisbarkeitspradikat fur eine Theorie T wenn es fur alle Formeln f ps displaystyle varphi psi nbsp folgende drei Bedingungen erfullt Wenn T f displaystyle T vdash varphi nbsp dann T B f displaystyle T vdash B varphi nbsp T B f ps B f B ps displaystyle T vdash B varphi rightarrow psi rightarrow B varphi rightarrow B psi nbsp T B f B B f displaystyle T vdash B varphi rightarrow B B varphi nbsp Es lasst sich zeigen dass eine Standard Reprasentation der Beweisbarkeit in einer Theorie wie der Peano Arithmetik oder der Mengenlehre diese drei Anforderungen erfullt und somit ein Beweisbarkeitspradikat ist Sei nun T eine Theorie die folgende Eigenschaften hat T besitzt ein Beweisbarkeitspradikat B Diagonalisierung In T hat jede Formel mit freier Variable einen Fixpunkt im folgenden Sinne Ist f x displaystyle varphi x nbsp eine Formel mit freier Variable x dann gibt es eine Formel ps displaystyle psi nbsp sodass gilt T ps f ps displaystyle T vdash psi leftrightarrow varphi psi nbsp das heisst ps displaystyle psi nbsp hat die intuitive Bedeutung Ich habe die Eigenschaft f x displaystyle varphi x nbsp Beweis Bearbeiten Mit den angegebenen Voraussetzungen lasst sich der Satz von Lob wie folgt beweisen 1 Sei f displaystyle varphi nbsp eine Formel mit T B f f displaystyle T vdash B varphi rightarrow varphi nbsp Durch Diagonalisierung erhalt man aus der Formel B x f displaystyle B x rightarrow varphi nbsp eine Formel ps displaystyle psi nbsp mit T ps B ps f displaystyle T vdash psi leftrightarrow B psi rightarrow varphi nbsp Wegen Axiom 1 ist T B ps B ps f displaystyle T vdash B psi rightarrow B psi rightarrow varphi nbsp Wegen Axiom 2 ist T B ps B ps f B ps B B ps f displaystyle T vdash B psi rightarrow B psi rightarrow varphi rightarrow B psi rightarrow B B psi rightarrow varphi nbsp Aus 3 und 4 folgt T B ps B B ps f displaystyle T vdash B psi rightarrow B B psi rightarrow varphi nbsp Wegen 2 und Axiom 2 ist T B B ps f B B ps B f displaystyle T vdash B B psi rightarrow varphi rightarrow B B psi rightarrow B varphi nbsp Aus 5 und 6 folgt T B ps B B ps B f displaystyle T vdash B psi rightarrow B B psi rightarrow B varphi nbsp Wegen Axiom 3 gilt T B ps B B ps displaystyle T vdash B psi rightarrow B B psi nbsp Aus 7 und 8 folgt T B ps B f displaystyle T vdash B psi rightarrow B varphi nbsp Aus 1 und 9 folgt T B ps f displaystyle T vdash B psi rightarrow varphi nbsp Aus 2 und 10 folgt T ps displaystyle T vdash psi nbsp Wegen Axiom 1 ist T B ps displaystyle T vdash B psi nbsp Aus 10 und 12 folgt nun T f displaystyle T vdash varphi nbsp Anwendungen BearbeitenEin Henkinsatz ist ein Satz der seine eigene Beweisbarkeit ausdruckt Der Satz von Lob zeigt dass jeder Henkinsatz insofern beweisbar ist dass er ein solcher ist beweisbar ist Denn wenn f displaystyle varphi nbsp ein Henkinsatz ist gilt T f B e w T f displaystyle T vdash varphi leftrightarrow Bew T varphi nbsp also nach dem Satz von Lob T f displaystyle T vdash varphi nbsp 2 P ist ein Wahrheitspradikat wenn fur alle Formeln f displaystyle varphi nbsp gilt T P f f displaystyle T vdash P varphi leftrightarrow varphi nbsp Es lasst sich leicht zeigen dass P auch ein Beweisbarkeitspradikat fur T ist Nach dem Satz von Lob gilt dann fur alle Formeln f displaystyle varphi nbsp T f displaystyle T vdash varphi nbsp und T ist inkonsistent Also besitzt keine konsistente Theorie ein Wahrheitspradikat 3 Der zweite godelsche Unvollstandigkeitssatz besagt dass ein hinreichend starkes und konsistentes formales System die eigene Konsistenz nicht beweisen kann Dies lasst sich wie folgt aus dem Satz von Lob folgern Angenommen T displaystyle T nbsp beweist die eigene Konsistenz d h T B e w T displaystyle T vdash neg Bew T bot nbsp Dies ist aquivalent zu T B e w displaystyle T vdash Bew bot rightarrow bot nbsp Nach dem Satz von Lob ist somit T displaystyle T vdash bot nbsp und T displaystyle T nbsp ist inkonsistent Literatur BearbeitenGeorge Boolos John P Burgess und Richard Jeffrey Computability and Logic 4 Auflage Cambridge University Press 2002 ISBN 0 521 70146 5 Martin Hugo Lob Solution of a Problem of Leon Henkin In Journal of Symbolic Logic Band 20 1955 S 115 118 Weblinks BearbeitenSatz von Lob bei PlanetMath The Cartoon Guide to Lob s Theorem von Eliezer YudkowskyEinzelnachweise Bearbeiten Boolos et al 2002 Seite 236 237 Boolos et al 2002 Seite 235 Boolos et al 2002 Seite 237 Abgerufen von https de wikipedia org w index php title Satz von Lob amp oldid 209366361