Gödel-Számozás egy
A formális számelméletben a Gödel-számozás egy olyan függvény, amely egy formális nyelv minden szimbólumához és formulájához egy egyedi természetes számot rendel, amelyet Gödel-számnak (GN) neveznek. A fogalmat először Kurt Gödel használta a befejezetlenségi tételének bizonyításához.
A gödeli számozás olyan kódolásként értelmezhető, amelyben egy matematikai jelölés minden szimbólumához egy számot rendelnek, és a természetes számok egy sora így valamilyen formát vagy függvényt reprezentálhat. A kiszámítható függvények halmazának számozása ezután Gödel-számok (más néven effektív számok) folyamával reprezentálható. Rogers ekvivalencia-tétele kritériumokat fogalmaz meg arra vonatkozóan, hogy a kiszámítható függvények halmazának mely számozásai Gödel-számozások.
Meghatározás
Adott egy megszámlálható S halmaz, a Gödel-számozás egy injektív függvény
f : S → N {\displaystyle f:S\to \mathbb {N} } 
mind f, mind f - 1{\displaystyle f^{-1}} 
(f inverze) kiszámítható függvények.
Példák
Alapjegyzetelés és karakterláncok
Az egyik legegyszerűbb Gödel-számozási séma mindennap használatos: Az egész számok és szimbólumsorozatként való ábrázolásuk közötti megfeleltetés. Például a 2 3 sorozatot egy bizonyos szabályrendszer szerint úgy értelmezzük, hogy az megfelel a huszonhárom számnak. Hasonlóképpen, az N szimbólumból álló ábécé szimbólumsorai kódolhatók úgy, hogy minden szimbólumot azonosítunk egy 0-tól N-ig terjedő számmal, és a sorozatot egy egész szám N+1 bázisú ábrázolásaként olvassuk.
Kérdések és válaszok
K: Mi az a gödeli számozás?
V: A Gödel-számozás egy olyan függvény, amely egy formális nyelv minden szimbólumához és formulájához egy egyedi természetes számot rendel, amelyet Gödel-számnak (GN) nevezünk.
K: Ki használta először a Gödel-számozás fogalmát?
V: Kurt Gödel használta először a Gödel-számozás fogalmát a befejezetlenségi tételének bizonyításához.
K: Hogyan értelmezhetjük a gödeli számozást?
V: A Gödel-számozást olyan kódolásként értelmezhetjük, amelyben egy matematikai jelölés minden szimbólumához egy számot rendelünk, és a természetes számok egy sora valamilyen formát vagy függvényt reprezentálhat.
K: Hogyan nevezzük a Gödel-számozás által hozzárendelt természetes számokat?
V: A Gödel-számozás által hozzárendelt természetes számokat Gödel-számoknak vagy effektív számoknak nevezzük.
K: Mit állít Rogers ekvivalencia-tétele?
V: A Rogers ekvivalencia-tétele olyan kritériumokat fogalmaz meg, amelyek alapján a kiszámítható függvények halmazának azon számozásai Gödel-számozások.
K: Mit reprezentál a Gödel-számok sorozata?
V: A kiszámítható függvények halmazának egy számozása Gödel-számok folyamával reprezentálható.
K: Miért fontos a Gödel-számozás a formális számelméletben?
V: A Gödel-számozás azért fontos a formális számelméletben, mert módot ad a matematikai formulák és függvények természetes számokként való ábrázolására, ami lehetővé teszi olyan fontos tételek bizonyítását, mint a befejezetlenségi tétel.
