Gödel-Isomorphismus
Der Gödel-Isomorphismus bezeichnet einen vom österreichischen Mathematiker Kurt Gödel erfundenen Isomorphismus, der als Hilfsmittel beim Beweis des gödelschen Unvollständigkeitssatzes dient. Mit dem Isomorphismus werden Sätze in formalen Systemen auf natürliche Zahlen abgebildet und die Regeln des formalen Systems auf mathematische Operationen.
Weitere Namen des Gödel-Isomorphismus sind Gödel-Nummerierung, Gödelisierung und Gödel-Operator.
Grundbegriffe
Ein Isomorphismus ist eine Abbildung, die umgekehrt werden kann. Also jedem Element der Ursprungsmenge wird genau ein Element der Zielmenge zugeordnet, so dass auch jedem Element der Zielmenge dann genau ein Element der Ursprungsmenge zugeordnet ist. Dadurch kann man dann einzelne Objekte durch Anwendung des Isomorphismus von einer Darstellung in die andere umwandeln und dies auch wieder umkehren. Ein Beispiel aus dem täglichen Leben wäre ein Restaurant: Bestellt der Gast beispielsweise Schnitzel, schreiben viele Kellner nur Nummern auf, z.B. 123. Der Küchenchef erhält nur diese Nummern, weiß aber dennoch, was er zu kochen hat. Dies funktioniert aber nur deshalb, weil jeder verwendeten Nummer nur ein Gericht, und jedem Gericht nur eine Nummer zugeordnet ist. Die Abbildung Gericht <--> Nummer ist daher ein Isomorphismus.
Ein formales System ist ein System, in dem Sätze nach bestimmten Regeln aus bereits vorhandenen Sätzen generiert werden können. Als Startmenge gelten dabei als wahr angenommene Sätze, so genannte Axiome.
Beispiel
Angenommen, beliebige Wörter der Sprache L, die auf dem Alphabet Σ basieren, sollen gödelisiert werden. Hier sei Σ = {a,b,c}. Als Gödelisierungsfunktion sei nun weiterhin die Funkion gewählt, die jeder Zahl aus 
eine Primzahl zuordnet, also p0 = 2,p1 = 3,p2 = 5,p3 = 7,.... Nun weist man den fortlaufenden Primzahlen Bedeutungen zu: ein "a" an erster Stelle hat den Wert p0 = 2, ein "b" an erster Stelle den Wert p1 = 3, ein "c" an erster Stelle den Wert p2 = 5. Ein "a" an zweiter Stelle bekommt nun den Wert p3 = 7 zugewiesen, ein "b" an zweiter Stelle p4 = 11 und so weiter. Die eigentliche Gödelisierung ist nun die Multiplikation aller Werte der einzelnen Buchstaben. Zum Beispiel:
Das Wort "abcba"
- Das "a" an erster Stelle hat den Wert p0 = 2
- Das "b" an zweiter Stelle hat den Wert p4 = 11
- Das "c" an dritter Stelle hat den Wert p8 = 23
- Das "b" an vierter Stelle hat den Wert p13 = 43
- Das "a" an fünfter Stelle hat den Wert p15 = 53
Die Gödelnummer für "abcba" lautet also 2 * 11 * 23 * 43 * 53 = 1153174
Eine Andere Möglichkeit der Kodierung wäre, den Buchstaben zunächst einfach fortlaufende Nummern zuzuweisen. Ein "a" entspäche der 1, ein "b" der 2 und ein "c" der 3. Nun kann man Gödelisieren, indem man die dem Buchstaben entsprechenden Potenzen der fortlaufenden Primzahlen miteinander multipliziert:
Das Wort "abccba"
- Das "a" an erster Stelle hat den Wert (p0)1 = 21 = 2
- Das "b" an zweiter Stelle hat den Wert (p1)2 = 32 = 9
- Das "c" an dritter Stelle hat den Wert (p2)3 = 53 = 125
- Das "c" an vierter Stelle hat den Wert (p3)3 = 73 = 343
- Das "b" an fünfter Stelle hat den Wert (p4)2 = 112 = 121
- Das "a" an sechster Stelle hat den Wert (p5)1 = 131 = 13
Die Gödelnummer für "abccba" in dieser Kodierung lautet also 2 * 9 * 125 * 343 * 121 * 13 = 1213962750