V teórii formálnych čísel je Gödelovo číslovanie funkcia, ktorá každému symbolu a formule nejakého formálneho jazyka priradí jedinečné prirodzené číslo nazývané Gödelovo číslo (GN). Tento pojem prvýkrát použil Kurt Gödel pri dôkaze svojej vety o neúplnosti. Gödelovo číslovanie možno chápať ako systém kódovania syntaxe formálneho systému tak, aby výroky o formálnych objektoch (napríklad „φ je dôkaz formule ψ“) bolo možné preložiť na výroky o prirodzených číslach.

Základná idea a interpretácia

V praktickom zmysle ide o dvojstupňový postup:

  • najprv sa každému základnému symbolu jazyka priradí malé prirodzené číslo (kód symbolu),
  • potom sa z postupnosti takýchto kódov konštruuje jediné prirodzené číslo, ktoré reprezentuje celú postupnosť (formulu, dôkaz alebo inú syntaktickú štruktúru).

Takéto číslovanie umožňuje „arithmetizovať“ syntax: otázky o formulách a dôkazoch sa dajú pretransformovať na otázky o prirodzených číslach a potom analyzovať metódami teórie čísel a výpočtovej teórie.

Konštrukcia (klasický príklad — prvočíselné kódovanie)

Najznámejšia a najintuitívnejšia konštrukcia využíva prvočíselnú faktorizáciu. Postup je nasledovný:

  1. Priradíme každému symbolu jazyka nejaké prirodzené číslo (kód symbolu).
  2. Pre postupnosť symbolov s kódmi c1, c2, ..., cn vytvoríme číslo
    GN = 2^{c1} · 3^{c2} · 5^{c3} · ... · p_n^{c_n}, kde p_k je k‑tým prvočíslom (2,3,5,7,...).

Vďaka fundamentálnej vete aritmetiky (jedinečnosť prvočíselnej faktorizácie) je takéto číslovanie jednoznačné: každej postupnosti kódov zodpovedá práve jedno prirodzené číslo a z čísla sa postupnosť dá spätne obnoviť faktorizáciou.

Príklad (ilustrácia): nech symboly „a“, „b“, „c“ majú kódy 1, 2, 3. Postupnosť (a,b,c) má GN = 2^1 · 3^2 · 5^3 = 2 · 9 · 125 = 2250. Z čísla 2250 odstránením prvočíselných mocnín vieme späť získať exponenty 1,2,3, a teda pôvodnú postupnosť.

Vlastnosti Gödelovho číslovania

  • Jedinečnosť: pri rozumnej konštrukcii (napr. pomocou prvočísel) každá rôzna syntaktická štruktúra dostane iné číslo.
  • Efektívnosť (výpočtovosť): konverzia medzi syntaktickou štruktúrou a jej Gödelovým číslom môže byť zvolená tak, aby bola výpočtovo efektívna (napr. primitívno­rekurzívna alebo aspoň rekurzívna). To znamená, že existuje algoritmus na získanie GN zo zápisu a naopak.
  • Flexibilita: číslovanie nie je jednoznačne dané — existuje mnoho rôznych Gödelových číslovaní, ktoré spĺňajú požiadavky efektivity a jedinečnosti. Dôležité je, že všetky rozumné (akceptovateľné) číslovania sú ekvivalentné z hľadiska ich mocnosti a použiteľnosti v logike (Rogersova veta o ekvivalencii).
  • Kompozitné kódovanie: okrem postupností sa dajú kódovať stromy, dôkazy, páry, funkcie a ďalšie syntaktické objekty.

Význam v matematike a logike

Gödelovo číslovanie je kľúčové pre formálne výsledky, ktoré spájajú syntax a aritmetiku:

  • Gödelova veta o neúplnosti: Gödel použil číslovanie na preklad tvrdení o formule do aritmetických výrokov, vďaka čomu konštruoval aritmetizovanú vetu, ktorá hovorí o svojej vlastnej nedokazateľnosti.
  • Samoodkazové konštrukcie: pomocou číslovania a diagonálnej metódy sa vytvárajú vety, ktoré „hovoria“ o svojom vlastnom Gödelovom čísle (self‑reference), čo je jadrom mnohých paradoxov a meta‑matematických argumentov.
  • Teória výpočtov a rekurzívne funkcie: číslovanie umožňuje efektívnu enumeráciu všetkých programov, Turingových strojov alebo vypočítateľných funkcií — tieto sú potom reprezentované prúdmi Gödelových čísel (nazývaných často efektívne čísla).
  • Dôkazová teória a formálne verifikácie: v modernom kontexte sa Gödelovo číslovanie používa pri formálnom zapise dôkazov, analýze ich komplexity a pri mechanickej verifikácii formálnych systémov.

Rogersova veta a akceptovateľné číslovania

Rogersova veta o ekvivalencii definuje kritériá, ktorým musí číslovanie množiny vypočítateľných funkcií vyhovovať, aby bolo považované za „Gödelovo číslovanie“ v zmysle ekvivalencie. V podstate ide o požiadavky na efektívnosť a schopnosť realizovať základné operácie nad kódmi (napríklad simuláciu spojenia funkcií alebo efektívne dekódovanie). Táto veta ukazuje, že rôzne prirodzené spôsoby číslovania vypočítateľných objektov sú v podstatnom zmysle ekvivalentné.

Zhrnutie

Gödelovo číslovanie je technika, ktorá prevádza syntaktické objekty formálneho jazyka na prirodzené čísla tak, aby sa syntax dala analyzovať aritmetickými prostriedkami. Je to základný nástroj v metamatematike, s použitím v dôkazoch o neúplnosti, v teórii výpočtov, pri tvorbe samoodkazových viet a v ďalších oblastiach logiky a informatiky. Hoci sa konkrétne číslovanie môže líšiť, dôležité sú jeho efektívne vlastnosti — dekódovanie a manipulácia s kódmi musia byť výpočtovo realizovateľné.