Anhang: Gödel’scher Unvollständigkeitssatz - Skizze des Originalbeweises

Eine Zahl kann Verschiedenes repräsentieren (wenn n  IN ein o  IN repräsentiert, so nennt man n auch Gödelnummer von o):

• 
  die Zahl selbst (25)
  
• 
  eine arithmetische Aussage (5 * 5 = 25)
  
• 
  einen Beweis für eine arithmetische Aussage (Folge von Aussagen, abhängig von Beweissystem)
  
• 
  Aussagen über Beweise (z.B. Beweis mit Codierung (= Gödelnummer) x beweist Aussage mit Gödelnummer y), usw.
  

Gödels Trick:

• 
  es ist entscheidbar, ob A ein Beweis für B ist (d.h. die char. Funktion f: IN  IN  {0,1} mit f(a,b) = 1 gdw. a Gödelnummer von Beweis für Formel mit Gödelnummer b ist, 0 sonst, ist berechenbar).
  
• 
  damit ist die Aussage „B ist (Gödelnummer eines) Beweis(es) für A“ arithmetisierbar, d.h. wir können das Prädikat beweist(a,b) repräsentieren, wobei a Gödelnummer eines Beweises und b Gödelnummer der durch ihn bewiesenen Aussage ist.
  
• 
  es ist entscheidbar, ob durch Substitution der freien Variablen in der Formel mit Gödelnummer x durch y die Formel mit Gödelnummer z entsteht (decodieren von x, Ersetzen der freien Variablen durch y, codieren, Vergleich mit z): das entsprechende Prädikat sub(x,y,z) ist damit arithmetisch repräsentierbar.
  
• 
  selbstsub(z,y) ist Abkürzung für sub(z,z,y): Substitution der eigenen Gödelnummer für die freie Variable in der Formel mit Gödelnummer z ergibt die Formel mit der Gödelnummer y.
  

Also sagt (G): (G) ist nicht beweisbar.

oder: Ich bin nicht beweisbar.
Nun gilt: Entweder (G) ist wahr: dann ist dieser Satz (G) nicht beweisbar,

=> also gibt es einen wahren Satz, der nicht beweisbar ist.

Oder (G) ist falsch: dann ist der Satz beweisbar,

=> also gibt es einen falschen Satz, der beweisbar ist.