next up previous
Next: Beweispaare Up: Goedelscher Unvollstaendigkeitssatz Previous: Goedelscher Unvollstaendigkeitssatz

Goedelisierung

Bedeutendste Leistung von Goedel in diesem Beweis ist die Entdeckung eines ganz besonderen Isomorphismus, die sogenannte Goedelisierung.

Def.: X sei endliches Alphabet

\( g:X^{*}\rightarrow N \) (nat. Zahlen), g(p) Goedelnummer von p

Eigenschaften der Abbildung:

  1. g injektiv
  2. g berechenbar (rekursiv)
  3. Umkehrung, d.h. \( G=\left\{ n\vert\exists p(g(p)=n\wedge p\epsilon X^{*}\right\} \) entscheidbar (Ist n Goedelnummer von p?)
  4. \( g^{-1}:G\rightarrow X^{*} \) berechenbar (rekursiv)
PA wird in sich selbst abgebildet...

Beispiel bringen... Isomorphismus erklaeren... Doppelte Bedeutung als Zeichenkette und natuerliche Zahl erklaeren... Bedeutung von primitiver Rekursion (festes Ende nach endlich vielen Schritten bekannt) erklaeren... Primzahlkodierung, Tupelcodierung usw. erwaehnen... PA kann ueber Zahlen sprechen, aber nicht ueber Zeichenketten


Lee Chuck 2001-05-01