Gödelovo číslovanie
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 interpretovať ako kódovanie, v ktorom je každému symbolu matematického zápisu priradené číslo a prúd prirodzených čísel potom môže reprezentovať nejaký tvar alebo funkciu. Číslovanie množiny vypočítateľných funkcií potom môže byť reprezentované prúdom Gödelových čísel (nazývaných aj efektívne čísla). Rogersova veta o ekvivalencii uvádza kritériá, pre ktoré sú tieto číslovania množiny vypočítateľných funkcií Gödelovými číslovaniami.
Definícia
Pri spočítateľnej množine S je Gödelovo číslovanie injekčná funkcia
f : S → N {\displaystyle f:S\to \mathbb {N} } 
s f aj f - 1{\displaystyle f^{-1}} 
(inverzná hodnota f) sú vypočítateľné funkcie.
Príklady
Základný zápis a reťazce
Jedna z najjednoduchších Gödelových číselných schém sa používa každý deň: Je to korešpondencia medzi celými číslami a ich reprezentáciami ako reťazcami symbolov. Napríklad postupnosť 2 3 sa podľa určitého súboru pravidiel chápe ako zodpovedajúca číslu dvadsaťtri. Podobne možno kódovať reťazce symbolov z nejakej abecedy N symbolov tak, že sa každý symbol identifikuje číslom od 0 do N a reťazec sa číta ako reprezentácia celého čísla v základe N+1.
Otázky a odpovede
Otázka: Čo je to Gödelovo číslovanie?
Odpoveď: Gödelovo číslovanie je funkcia, ktorá každému symbolu a formule formálneho jazyka priraďuje jedinečné prirodzené číslo, nazývané Gödelovo číslo (GN).
Otázka: Kto ako prvý použil pojem Gödelovo číslovanie?
Odpoveď: Kurt Gödel prvýkrát použil koncept Gödelovho číslovania pri dôkaze svojej vety o neúplnosti.
Otázka: Ako môžeme interpretovať Gödelovo číslovanie?
Odpoveď: Gödelovo číslovanie môžeme interpretovať ako kódovanie, v ktorom je každému symbolu matematického zápisu priradené číslo a prúd prirodzených čísel môže predstavovať nejaký tvar alebo funkciu.
Otázka: Ako nazývame prirodzené čísla priradené Gödelovým číslovaním?
Odpoveď: Prirodzené čísla priradené Gödelovým číslovaním sa nazývajú Gödelove čísla alebo efektívne čísla.
Otázka: Čo hovorí Rogersova veta o ekvivalencii?
Odpoveď: Rogersova veta o ekvivalencii uvádza kritériá, pre ktoré sú tie číslovania množiny vypočítateľných funkcií Gödelovými číslovaniami.
Otázka: Čo predstavuje prúd Gödelových čísel?
Odpoveď: Číslovanie množiny vypočítateľných funkcií môže byť reprezentované prúdom Gödelových čísel.
Otázka: Prečo je Gödelovo číslovanie dôležité vo formálnej teórii čísel?
Odpoveď: Gödelovo číslovanie je dôležité vo formálnej teórii čísel, pretože poskytuje spôsob reprezentácie matematických vzorcov a funkcií ako prirodzených čísel, čo umožňuje dôkaz dôležitých tvrdení, ako je veta o neúplnosti.
