Gödel-Isomorphismus

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

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.

[Bearbeiten] Grundbegriffe

Ein Isomorphismus ist eine Abbildung, die umgekehrt werden kann. Also wird jedem Element der Ursprungsmenge genau ein Element der Zielmenge zugeordnet, so dass auch jedem Element der Zielmenge genau ein Element der Ursprungsmenge zugeordnet ist. Dadurch kann man 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.

[Bearbeiten] 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 Funktion gewählt, die jeder Zahl aus $\mathbb{N}^+$ eine Primzahl zuordnet, also $p 0 = 2, p 1 = 3, p 2 = 5, p 3 = 7,...$ . Nun weist man den fortlaufenden Primzahlen Bedeutungen zu: ein "a" an erster Stelle hat den Wert $p 0 = 2$ , ein "b" an erster Stelle den Wert $p 1 = 3$ , ein "c" an erster Stelle den Wert $p 2 = 5$ . Ein "a" an zweiter Stelle bekommt nun den Wert $p 3 = 7$ zugewiesen, ein "b" an zweiter Stelle $p 4 = 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 $p 0 = 2$
Das "b" an zweiter Stelle hat den Wert $p 4 = 11$
Das "c" an dritter Stelle hat den Wert $p 8 = 23$
Das "b" an vierter Stelle hat den Wert $p 10 = 31$
Das "a" an fünfter Stelle hat den Wert $p 12 = 41$

Die Gödelnummer für "abcba" lautet also $2 * 11 * 23 * 31 * 41 = 643126$

Eine andere Möglichkeit der Kodierung wäre, den Buchstaben zunächst einfach fortlaufende Nummern zuzuweisen. Ein "a" entsprä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"