Der Gödelsche Unvollständigkeitssatz

Der Gödelsche Unvollständigkeitssatz

Kurt Gödel (*1906 in Brünn, gehörte dem berühmten Wiener Kreis an, †1978 in Princeton), Mathematiker und Logiker, oft als der bedeutendste Logiker des 20. Jahrhunderts angesehen.

Beschäftigte sich mit Grenzen der Beweisbarkeit. Hauptresultat: jedes konsistente Beweissystem für die Arithmetik ist unvollständig: es gibt wahre Sätze der Arithmetik, die man in dem System nicht beweisen kann.

Erhebliche Bedeutung für die Grundlagen der Mathematik/Informatik. Widerlegt das Hilbertsche Programm (David Hilbert, 1862-1943, Göttingen), durch das die gesamte Mathematik auf die Arithmetik zurückgeführt und auf ein axiomatisches System gestellt werden sollte, aus dem alle mathematischen Sätze streng ableitbar sind.

1. 
   jede natürliche Zahl n (repräsentiert durch Symbole 0, 1, 2, …) ist ein Term,
   
2. 
   jede Variable ist ein Term,
   
3. 
   wenn t₁ und t₂ Terme sind, so sind (t₁ + t₂) und (t₁ * t₂) Terme.
   

Die Symbole + und * haben eine feste Interpretation, nämlich Addition und Multiplikation auf den natürlichen Zahlen. Freie und gebundene Variablen sind wie üblich definiert (die letzteren liegen im Bereich eines Quantors). Eine Belegung  ordnet jeder Variablen eine natürliche Zahl als Wert zu. Falls t Term ist, dann ist (t) die Zahl, die sich ergibt, wenn jede Variable x in t durch (x) ersetzt und dann „ausgerechnet“ wird.

1. 
   F' = (t₁ = t₂) und t₁ wird zu derselben natürlichen Zahl ausgewertet wie t₂.
   
2. 
   F' = F und F ist nicht wahr.
   
3. 
   F' = (F  G) und F wahr und G wahr.
   
4. 
   F' = (F  G) und F wahr oder G wahr.
   
5. 
   F' = x F und es gibt ein n, so dass F(x/n) wahr (Substitution von x durch n in F).
   
6. 
   F' = x F und für alle n ist F(x/n) wahr.
   

Beispiele:

2 + 3 = 5, x y (x + y) = (y + x), x y z (x = (y + z)) sind wahre arithmetische Formeln.
Hinweis: für jede geschlossene arithmetische Formel F gilt: entweder F  WA oder F  WA.
Def.: Die Funktion f: IN ^k -> IN ist arithmetisch repräsentierbar, falls es eine arithmetische Formel F(x₁, ..., x_k, y) gibt, so dass f(n₁, ..., n_k) = m gdw. F(n₁, ..., n_k, m) wahr ist.
Beispiel: Sei (a < b) Abkürzung für:  z (a + z + 1 = b)
DIV:  r ((r < x₂)  (x₁ = y * x₂ + r))

MOD:  k ((y < x₂)  (x₁ = k * x₂ + y))

Sei A rekursiv aufzählbare, aber nicht entscheidbare Sprache (etwa H, PCP, ...). Die halbe charakteristische Funktion von A ist WHILE-berechenbar und damit arithmetisch repräsentierbar durch eine Formel F(x,y). Es gilt:

 F(n,1) ist wahr

 F(n,1)  WA
Da die Funktion, die jedem n die Formel F(n,1) zuordnet, total und berechenbar ist, wird dadurch A auf WA reduziert. Da A nach Voraussetzung nicht entscheidbar ist, kann es auch WA nicht sein. Damit ist WA auch nicht rekursiv aufzählbar.
Hinweis: wir sind im Beweis davon ausgegangen, dass A schon in codierter Form als Menge natürlicher Zahlen vorliegt. Dass so etwas immer möglich ist, haben wir am Anfang von Teil II diskutiert.
(PS: der Beweis funktioniert nicht für allgemeine Prädikatenlogik, da dort nicht gilt: F allgemeingültig oder F allgemeingültig.)
b) Beweissysteme
Ein Beweissystem (Kalkül) besteht üblicher Weise aus einer Formelsprache, einer Menge von Axiomen aus dieser Sprache und einer Menge von Ableitungsregeln (etwa modus ponens: aus p und p  q leite q ab). Ein formaler Beweis ist dann eine Folge von Formeln, wobei jede Formel in der Folge entweder ein Axiom ist (ohne Herleitung gültig) oder sich aus vorhergehenden Formeln durch Anwendung einer Regel erzeugen lässt. Die bewiesene Formel ist dann die letzte in der Folge.
Ein Beweissystem ist immer ein System für eine bestimmte Teilmenge A von Formeln (Beispiel: Beweissystem für die aussagenlogischen Tautologien). Es heißt korrekt, wenn es nur Beweise für Formeln in A gibt, vollständig, wenn alle Formeln in A bewiesen werden können.
Beispiel: Kalkül für aussagenlogische Tautologien (Lukasiewicz). Nur  und  verwendet, p  q kann durch p  q ausgedrückt werden, p  q durch (p  q).

Axiome: alle Instanzen der folgenden Ausdrücke

(für p, q und r können beliebige aussagenlogische Formeln substituiert werden):
p  (q  p)

(p  (q  r))  ((p  q) (p  r))

(p  q)  (q  p)
Inferenzregel: Modus ponens. Korrekt und vollständig für aussagenlogische Tautologien.
Wir abstrahieren hier so weit wie möglich von konkreten Kalkülen. Wir benötigen hier nur 2 minimale Anforderungen an Beweissysteme, nämlich dass man entscheiden kann, ob etwas tatsächlich ein Beweis ist, und dass man für jeden Beweis berechnen kann, was er beweist:
Def.: Ein Beweissystem für A  * ist ein Paar (B, F), wobei gilt:

1. 
   B  * ist eine entscheidbare Menge, die Menge der Beweise.
   
2. 
   F: B -> * ist eine totale berechenbare Funktion, die jedem Beweis das durch ihn bewiesene Element aus * zuordnet.
   

(B, F) heißt korrekt (für A), wenn für alle b  B gilt: F(b)  A.

vollständig (für A), wenn für a  A ein b  B existiert mit F(b) = a.

Satz (Gödelscher Unvollständigkeitssatz):

Jedes Beweissystem für WA ist inkorrekt oder unvollständig.
Beweis: Angenommen (B, F) wäre vollständig und korrekt für WA. Dann könnte man WA aufzählen, indem man alle Beweise b  B (die wegen der Entscheidbarkeit von B auch aufzählbar sein müssen) der Reihe nach generiert und F(b) ausgibt. WA ist aber, wie bereits bewiesen, nicht rekursiv aufzählbar.
Äquivalente Formulierungen:

Jedes vollständige Beweissystem für WA ist inkorrekt

Jedes vollständige Beweissystem für WA ist inkonsistent (da vollständig und inkorrekt impliziert inkonsistent)

Jedes konsistente Beweissystem für WA ist unvollständig.