Gödelnummer
In de formele getaltheorie is een Gödelnummering een functie die aan elk symbool en elke formule van een formele taal een uniek natuurlijk getal toekent, dat een Gödelgetal (GN) wordt genoemd. Het concept werd voor het eerst gebruikt door Kurt Gödel voor het bewijs van zijn onvolledigheidstheorema.
Een Gödel-nummering kan worden opgevat als een codering waarbij aan elk symbool van een wiskundige notatie een getal wordt toegekend, en een stroom van natuurlijke getallen kan dan een of andere vorm of functie voorstellen. Een nummering van de verzameling berekenbare functies kan dan worden voorgesteld door een stroom Gödel-nummers (ook wel effectieve getallen genoemd). De gelijkwaardigheidstheorem van Rogers stelt criteria op grond waarvan die nummeringen van de verzameling berekenbare functies Gödel-nummeringen zijn.
Definitie
Gegeven een aftelbare verzameling S, is een Gödelnummering een injectieve functie
f : S → N {Stijl f:S naar \mathbb {N}} } 
met zowel f als f - 1 {\displaystyle f^{-1}} 
(de inverse van f) berekenbare functies zijn.
Voorbeelden
Basisnotatie en strings
Een van de eenvoudigste nummeringsschema's van Gödel wordt dagelijks gebruikt: De overeenkomst tussen gehele getallen en hun representaties als reeksen symbolen. Zo wordt bijvoorbeeld de rij 2 3 volgens een bepaalde reeks regels geacht overeen te komen met het getal drieëntwintig. Evenzo kunnen reeksen symbolen uit een alfabet van N symbolen worden gecodeerd door elk symbool te identificeren met een getal van 0 tot N en de reeks te lezen als de basis N+1 voorstelling van een geheel getal.
Vragen en antwoorden
V: Wat is een Gödel-nummering?
A: Een Gödel-nummering is een functie die een uniek natuurlijk getal toekent aan elk symbool en elke formule van een formele taal, een Gödel-nummer (GN) genaamd.
V: Wie gebruikte het concept van Gödel nummering voor het eerst?
A: Kurt Gödel gebruikte het concept van Gödel-nummering voor het eerst voor het bewijs van zijn onvolledigheidstheorema.
V: Hoe kunnen we Gödel nummering interpreteren?
A: We kunnen Gödel-nummering interpreteren als een codering waarbij aan elk symbool van een wiskundige notatie een nummer wordt toegekend, en een stroom van natuurlijke getallen kan een bepaalde vorm of functie voorstellen.
V: Hoe noemen we de natuurlijke getallen die door een Gödel-nummering worden toegekend?
A: De natuurlijke getallen die toegekend worden door een Gödel-nummering worden Gödel-nummers of effectieve getallen genoemd.
V: Wat stelt de equivalentietheorie van Rogers?
A: De equivalentietheorema van Rogers stelt criteria voor welke nummeringen van de verzameling berekenbare functies Gödel-nummeringen zijn.
V: Wat wordt voorgesteld door een stroom Gödel getallen?
A: Een nummering van de verzameling berekenbare functies kan voorgesteld worden door een stroom van Gödel getallen.
V: Waarom is Gödel nummering belangrijk in de formele getaltheorie?
A: Gödel-nummering is belangrijk in de formele getaltheorie omdat het een manier biedt om wiskundige formules en functies als natuurlijke getallen weer te geven, waardoor belangrijke stellingen zoals de onvolledigheidstheorie bewezen kunnen worden.
