Номерирането на Гьодел
В теорията на формалните числа номерирането на Гьодел е функция, която приписва на всеки символ и формула на някакъв формален език уникално естествено число, наречено число на Гьодел (GN). Концепцията е използвана за първи път от Курт Гьодел за доказване на неговата теорема за непълнота.
Номерирането на Гьодел може да се тълкува като кодиране, при което на всеки символ от математическия запис се присвоява число и тогава потокът от естествени числа може да представлява някаква форма или функция. Номерирането на множеството от изчислими функции може да бъде представено чрез поток от числа на Гьодел (наричани също ефективни числа). Теоремата за еквивалентност на Роджърс посочва критериите, по които тези номерирания на множеството от изчислими функции са номерирания на Гьодел.
Определение
При дадено преброимо множество S, номерирането на Гьодел е инжективна функция
f : S → N {\displaystyle f:S\to \mathbb {N} } 
както с f, така и с f - 1{\displaystyle f^{-1}} 
(обратната на f) са изчислими функции.
Примери
Базов запис и низове
Една от най-простите схеми за номериране на Гьодел се използва всеки ден: Съответствието между целите числа и техните представяния като низове от символи. Например последователността 2 3 се разбира, че чрез определен набор от правила съответства на числото двадесет и три. По подобен начин низове от символи от някаква азбука от N символа могат да бъдат кодирани, като всеки символ се идентифицира с число от 0 до N и низът се чете като представяне на цяло число в база N+1.
Въпроси и отговори
Въпрос: Какво представлява номерацията на Гьодел?
О: Номерирането на Гьодел е функция, която приписва уникално естествено число на всеки символ и формула на формален език, наречено число на Гьодел (GN).
Въпрос: Кой пръв използва концепцията за номерация на Гьодел?
О: Курт Гьодел използва за първи път концепцията за номерацията на Гьодел при доказването на своята теорема за непълнота.
В: Как можем да тълкуваме номерацията на Гьодел?
О: Можем да интерпретираме номерацията на Гьодел като кодиране, при което на всеки символ от математическата нотация се присвоява число, а потокът от естествени числа може да представлява някаква форма или функция.
Въпрос: Как наричаме естествените числа, присвоени от номерирането на Гьодел?
О: Естествените числа, присвоени от номерирането на Гьодел, се наричат числа на Гьодел или ефективни числа.
В: Какво гласи теоремата за еквивалентност на Роджърс?
О: Теоремата за еквивалентност на Роджърс посочва критериите, по които тези номерирания на множеството от изчислими функции са номерирания на Гьодел.
В: Какво представлява потокът от числа на Гьодел?
О: Номерирането на множеството от изчислими функции може да бъде представено чрез поток от числа на Гьодел.
В: Защо номерирането на Гьодел е важно във формалната теория на числата?
О: Номерирането на Гьодел е важно за формалната теория на числата, тъй като осигурява начин за представяне на математически формули и функции като естествени числа, което позволява доказването на важни теореми като теоремата за непълнота.
