Gödel-Zahlen
Die Gödel-Nummerierung ist eine grundlegende Technik, die jedem Symbol, jeder Formel und jedem Beweis einer formalen Sprache eine eindeutige natürliche Zahl (eine Gödel-Zahl) zuordnet. Diese Arithmetisierung der Syntax ermöglicht es, metamathematische Aussagen über ein formales System (z. B. „Diese Formel ist beweisbar“) als arithmetische Aussagen über Zahlen zu kodieren, die dann innerhalb des Systems selbst untersucht werden können.
Die Gödel-Nummerierung ist ein genialer Mechanismus, der die Lücke zwischen Syntax (der symbolischen Struktur einer formalen Sprache) und Zahlentheorie (den Eigenschaften ganzer Zahlen) schließt. Sie ermöglicht es, logische Aussagen in Aussagen über Zahlen zu übersetzen. Die Methode funktioniert, indem jedem Basissymbol der formalen Sprache zunächst eine eindeutige ganze Zahl zugeordnet wird (z. B. ¬ → 1, ∨ → 2, ∀ → 3, x → 4 usw.).
A formula, which is a sequence of these symbols, can then be assigned its own unique number. Gödel’s original method used prime factorization. For a sequence of symbols with numbers [latex]s_1, s_2, …, s_k[/latex], the formula’s Gödel number would be [latex]2^{s_1} \cdot 3^{s_2} \cdot 5^{s_3} \cdot \dots \cdot p_k^{s_k}[/latex], where [latex]p_k[/latex] is the k-th prime number. Due to the fundamental theorem of arithmetic (unique prime factorization), this mapping is injective; every formula gets a unique number, and from any such number, the original formula can be uniquely recovered.
Schließlich lässt sich ein Beweis, also eine Folge von Formeln, auf dieselbe Weise kodieren, indem man die Gödelzahlen seiner Bestandteile bestimmt und die Primzahlpotenzkodierung erneut anwendet. Diese vollständige Arithmetisierung bewirkt, dass komplexe metamathematische Eigenschaften, wie etwa „Die Folge F ist ein gültiger Beweis der Formel P“, zu rein arithmetischen Prädikaten werden, die die Gödelzahlen von F und P beinhalten. Dies erlaubte Gödel, eine Formel zu konstruieren, die auf ihre eigene Beweisbarkeit verweist – der entscheidende Schritt in seinem Unvollständigkeitsbeweis.
UNESCO Nomenclature: 1201
– Reine Mathematik
Verwendung
Konzeptuell/Theoretisch
Vorläufer
- analytische Geometrie (Descartes‘ Abbildung der Geometrie auf die Algebra)
- Leibniz' Konzept einer 'characteristica universalis'
- Der Fundamentalsatz der Arithmetik (eindeutige Primfaktorzerlegung)
- Formalisierung von Sprachen in der Logik durch Frege und Russell
- Cantors Arbeit über Abbildungen zwischen Mengen
Anwendungen
- Berechenbarkeitstheorie (Darstellung von Turingmaschinen und Programmen als Zahlen)
- Informatik (das Prinzip, dass Code Daten sind)
- Informationstheorie
- Kryptographie
- Theorie formaler Sprachen
- Beweise für Unentscheidbarkeit, wie zum Beispiel das Halteproblem
Potenzielle Innovationsideen
Aufgrund des hohen Datenverkehrs durch Web-Scraping-Bots, der derzeit mehr als 40.000 Anfragen pro Tag umfasst, ist dieser Inhalt ausschließlich Community-Mitgliedern vorbehalten.
> Anmelden < oder > Registrieren < (100% kostenlos) Zugriff darauf sowie auf alle anderen eingeschränkten Inhalte und Tools.
Verwandt mit: Gödel-Zahl, Arithmetisierung, Syntax, Metamathematik, Kodierung, formale Sprache, Beweistheorie, Berechenbarkeit, Selbstreferenz, Primfaktorzerlegung.