Gödelnummer

In de wiskundige logica is een Gödelnummer een uniek natuurlijk getal dat wordt toegewezen aan elk symbool of elke formule binnen een formele taal.

Dit concept werd voor het eerst door Kurt Gödel gebruikt in het bewijs van zijn Onvolledigheidsstelling van Gödel.

Gödelnummering

Gödelnummering kan gezien worden als een codering waarbij aan elk symbool van een wiskundige notatie een getal wordt toegekend. Elke formule in het systeem, en elke serie uitspraken in het systeem, kunnen zo gerepresenteerd worden door een reeks natuurlijke getallen. Zo'n reeks natuurlijke getallen kan zelf weer op een unieke manier door een enkel natuurlijk getal worden gerepresenteerd, dat het Gödelnummer van de formule of uitspraak wordt genoemd.

Gödels codering

Gödel zelf gebruikte een systeem van Gödelnummering gebaseerd op ontbinding in priemfactoren. Aan elk symbool $s\,$ dat voor wiskundige notatie in een systeem gebruikt kan worden kende hij een uniek getal $x\,$ toe. Elke uitspraak $s_{1}s_{2}s_{3}\dots s_{n}\,$ codeerde hij vervolgens door hier het unieke getal $2^{x_{1}}\cdot 3^{x_{2}}\cdot 5^{x_{3}}\cdot \dots \cdot {p_{n}}^{x_{n}}$ aan toe te kennen, waarbij $p_{n}\,$ het $n$-de priemgetal is. Elk getal dat op deze wijze verkregen wordt, kan op unieke wijze worden terugvertaald naar de oorspronkelijke uitspraak, door middel van ontbinding van het getal in priemfactoren.

Voorbeeld

Als simpel voorbeeld nemen we een wiskundige notatie die alleen uit de symbolen $a$, $b$ en $=$ bestaat. Aan deze symbolen kennen we respectievelijk de getallen 1, 2 en 3 toe. Om het Gödelnummer van bijvoorbeeld de formule $a=b$ te bepalen, zetten we deze notatie om in de bijbehorende reeks getallen 1, 3, 2 en gebruiken deze reeks om de opvolgende priemmachten te berekenen: $2^{1}\cdot 3^{3}\cdot 5^{2}$. Het resultaat is $2\cdot 27\cdot 25=1350$, het Gödelnummer voor deze formule.

Wat is in deze notatie de formule met Gödelnummer 540? Hiertoe ontbinden we 540 in priemfactoren: $540=2\cdot 2\cdot 3\cdot 3\cdot 3\cdot 5=2^{2}\cdot 3^{3}\cdot 5^{1}$. De reeks van machten van de priemfactoren is hier dus 2, 3, 1 wat omgezet de notatie $b=a$ oplevert.