Gödelnummer

Autor: Leandro Alegsa

01-11-2021

In der formalen Zahlentheorie ist eine Gödel-Nummerierung eine Funktion, die jedem Symbol und jeder Formel einer formalen Sprache eine eindeutige natürliche Zahl zuweist, die als Gödel-Zahl (GN) bezeichnet wird. Das Konzept wurde zuerst von Kurt Gödel für den Beweis seines Unvollständigkeitssatzes verwendet.

Eine Gödel-Nummerierung kann als eine Kodierung interpretiert werden, bei der jedem Symbol einer mathematischen Notation eine Zahl zugeordnet wird, und ein Strom natürlicher Zahlen kann dann eine Form oder Funktion darstellen. Eine Numerierung der Menge der berechenbaren Funktionen kann dann durch einen Strom von Gödel-Zahlen (auch effektive Zahlen genannt) dargestellt werden. Das Rogers'sche Äquivalenztheorem gibt Kriterien an, für die diese Nummerierungen der Menge der berechenbaren Funktionen Gödel-Numerierungen sind.

Definition

Bei einer zählbaren Menge S ist eine Gödel-Nummerierung eine injektive Funktion

f : S → N {\darstellungsstil f:S\bis \mathbb {N} } $f:S\to \mathbb {N}$

mit sowohl f als auch f - 1 {\Anzeigestil f^{-1}} $f^{-1}$ (die Inverse von f) sind berechenbare Funktionen.

Beispiele

Basisnotation und Zeichenketten

Eines der einfachsten Gödel-Numerierungsschemata wird täglich verwendet: Die Entsprechung zwischen ganzen Zahlen und ihren Darstellungen als Zeichenketten. So wird z.B. die Folge 2 3 nach einem bestimmten Regelwerk so verstanden, dass sie der Zahl dreiundzwanzig entspricht. In ähnlicher Weise können Zeichenketten aus einem Alphabet von N Symbolen kodiert werden, indem man jedes Symbol mit einer Zahl von 0 bis N identifiziert und die Zeichenkette als die Basis N+1-Repräsentation einer ganzen Zahl liest.

Fragen und Antworten

F: Was ist eine Gödelsche Nummerierung?

A: Eine Gödel-Nummerierung ist eine Funktion, die jedem Symbol und jeder Formel einer formalen Sprache eine eindeutige natürliche Zahl zuordnet, die sogenannte Gödel-Zahl (GN).

F: Wer hat das Konzept der Gödelschen Nummerierung zuerst verwendet?

A: Kurt Gödel hat das Konzept der Gödelschen Nummerierung erstmals für den Beweis seines Unvollständigkeitssatzes verwendet.

F: Wie können wir die Gödelsche Nummerierung interpretieren?

A: Wir können die Gödelsche Nummerierung als eine Kodierung interpretieren, bei der jedem Symbol einer mathematischen Notation eine Zahl zugewiesen wird, und ein Strom natürlicher Zahlen kann eine Form oder Funktion darstellen.

F: Wie nennen wir die natürlichen Zahlen, die durch eine Gödel-Nummerierung zugewiesen werden?

A: Die natürlichen Zahlen, die durch eine Gödel-Nummerierung zugewiesen werden, nennt man Gödel-Zahlen oder effektive Zahlen.

F: Was besagt das Rogers'sche Äquivalenztheorem?

A: Das Äquivalenztheorem von Rogers gibt Kriterien an, nach denen die Nummerierungen der Menge der berechenbaren Funktionen Gödel-Nummerierungen sind.

F: Was wird durch einen Strom von Gödel-Zahlen dargestellt?

A: Eine Nummerierung der Menge der berechenbaren Funktionen kann durch einen Strom von Gödel-Zahlen dargestellt werden.

F: Warum ist die Gödelsche Nummerierung in der formalen Zahlentheorie wichtig?

A: Die Gödelsche Nummerierung ist in der formalen Zahlentheorie wichtig, da sie eine Möglichkeit bietet, mathematische Formeln und Funktionen als natürliche Zahlen darzustellen, was den Beweis wichtiger Theoreme wie des Unvollständigkeitssatzes ermöglicht.