Gödelovo číslování
V teorii formálních čísel je Gödelovo číslování funkce, která každému symbolu a formuli nějakého formálního jazyka přiřazuje jedinečné přirozené číslo nazývané Gödelovo číslo (GN). Tento pojem poprvé použil Kurt Gödel při důkazu své věty o neúplnosti.
Gödelovo číslování lze interpretovat jako kódování, kdy je každému symbolu matematického zápisu přiřazeno číslo a proud přirozených čísel pak může reprezentovat nějaký tvar nebo funkci. Číslování množiny vypočitatelných funkcí pak může být reprezentováno proudem Gödelových čísel (nazývaných také efektivní čísla). Rogersova věta o ekvivalenci uvádí kritéria, pro která jsou tato číslování množiny vypočitatelných funkcí Gödelovými čísly.
Definice
Při dané spočetné množině S je Gödelovo číslování injektivní funkce
f : S → N {\displaystyle f:S\to \mathbb {N} } 
s f i f - 1{\displaystyle f^{-1}} 
(inverzní funkce f) jsou vypočitatelné funkce.
Příklady
Základní notace a řetězce
Jedno z nejjednodušších Gödelových číselných schémat se používá každý den: V tomto případě se jedná o korespondenci mezi celými čísly a jejich reprezentacemi v podobě řetězců symbolů. Například posloupnost 2 3 je podle určitého souboru pravidel chápána jako odpovídající číslu dvacet tři. Podobně lze řetězce symbolů z nějaké abecedy o N symbolech kódovat ztotožněním každého symbolu s číslem od 0 do N a čtením řetězce jako reprezentace celého čísla o základu N+1.
Otázky a odpovědi
Otázka: Co je to Gödelovo číslování?
Odpověď: Gödelovo číslování je funkce, která každému symbolu a formuli formálního jazyka přiřazuje jedinečné přirozené číslo, nazývané Gödelovo číslo (GN).
Otázka: Kdo jako první použil pojem Gödelovo číslování?
Odpověď: Kurt Gödel poprvé použil koncept Gödelova číslování pro důkaz své věty o neúplnosti.
Otázka: Jak můžeme interpretovat Gödelovo číslování?
Odpověď: Gödelovo číslování můžeme interpretovat jako kódování, v němž je každému symbolu matematického zápisu přiřazeno číslo a proud přirozených čísel může představovat nějaký tvar nebo funkci.
Otázka: Jak nazýváme přirozená čísla přiřazená Gödelovým číslováním?
Odpověď: Přirozená čísla přiřazená Gödelovým číslováním se nazývají Gödelova čísla nebo efektivní čísla.
Otázka: Co říká Rogersova věta o ekvivalenci?
Odpověď: Rogersova věta o ekvivalenci uvádí kritéria, pro která jsou ta číslování množiny spočitatelných funkcí Gödelova číslování.
Otázka: Co představuje proud Gödelových čísel?
Odpověď: Číslování množiny vypočitatelných funkcí lze reprezentovat proudem Gödelových čísel.
Otázka: Proč je Gödelovo číslování důležité ve formální teorii čísel?
Odpověď: Gödelovo číslování je ve formální teorii čísel důležité, protože poskytuje způsob, jak reprezentovat matematické formule a funkce jako přirozená čísla, což umožňuje důkaz důležitých tvrzení, jako je věta o neúplnosti.
