Gödelin numerointi
Muodollisessa lukuteoriassa Gödelin numerointi on funktio, joka antaa jokaiselle jonkin muodollisen kielen symbolille ja kaavalle ainutlaatuisen luonnollisen luvun, jota kutsutaan Gödelin luvuksi (GN). Käsitettä käytti ensimmäisen kerran Kurt Gödel todistaessaan epätäydellisyysteoriansa.
Gödelin numerointi voidaan tulkita koodaukseksi, jossa jokaiselle matemaattisen merkintätavan symbolille annetaan numero, jolloin luonnollisten lukujen virta voi edustaa jotakin muotoa tai funktiota. Laskettavissa olevien funktioiden joukon numerointi voidaan tällöin esittää Gödelin lukujen virralla (joita kutsutaan myös tehollisluvuiksi). Rogersin ekvivalenssiteoreemi esittää kriteerit sille, mitkä laskettavien funktioiden joukon numeroinnit ovat Gödelin numerointeja.
Määritelmä
Kun on annettu laskettava joukko S, Gödelin numerointi on injektiivinen funktio
f : S → N {\displaystyle f:S\to \mathbb {N} } 
sekä f että f - 1{\displaystyle f^{-1}} kanssa. 
(f:n käänteisluku) ovat laskettavissa olevia funktioita.
Esimerkkejä
Perusnotaatio ja merkkijonot
Yksi yksinkertaisimmista Gödelin numerointijärjestelmistä on käytössä päivittäin: Kokonaislukujen ja niiden symbolijonoina olevien esitystapojen välinen vastaavuus. Esimerkiksi lukujono 2 3 ymmärretään tietyn säännöstön mukaan vastaamaan lukua kaksikymmentäkolme. Vastaavasti symbolijonot jostakin N symbolin aakkosesta voidaan koodata tunnistamalla jokainen symboli numerolla 0-N ja lukemalla merkkijono kokonaisluvun N+1 esityksenä.
Kysymyksiä ja vastauksia
K: Mikä on Gödelin numerointi?
A: Gödelin numerointi on funktio, joka antaa jokaiselle formaalin kielen symbolille ja kaavalle ainutlaatuisen luonnollisen luvun, jota kutsutaan Gödelin luvuksi (GN).
K: Kuka käytti ensimmäisenä Gödelin numeroinnin käsitettä?
V: Kurt Gödel käytti ensimmäisenä Gödelin numeroinnin käsitettä todistaessaan epätäydellisyysteoriansa.
K: Miten voimme tulkita Gödelin numerointia?
V: Voimme tulkita Gödelin numeroinnin koodaukseksi, jossa matemaattisen merkintätavan jokaiselle symbolille annetaan numero, ja luonnollisten lukujen virta voi edustaa jotakin muotoa tai funktiota.
K: Miksi kutsumme Gödelin numeroinnin osoittamia luonnollisia lukuja?
V: Gödelin numeroinnin osoittamia luonnollisia lukuja kutsutaan Gödelin luvuiksi tai tehollisluvuiksi.
K: Mitä Rogersin ekvivalenssiteoria sanoo?
V: Rogersin ekvivalenssiteoreemi esittää kriteerit, joiden perusteella laskettavien funktioiden joukon numeroinnit ovat Gödelin numerointeja.
K: Mitä Gödelin lukujen virta edustaa?
V: Laskettavien funktioiden joukon numerointi voidaan esittää Gödelin lukujen virtana.
K: Miksi Gödelin numerointi on tärkeä formaalissa lukuteoriassa?
V: Gödelin numerointi on tärkeää formaalissa lukuteoriassa, koska se tarjoaa tavan esittää matemaattiset kaavat ja funktiot luonnollisina lukuina, mikä mahdollistaa tärkeiden teoreemojen, kuten epätäydellisyysteorian, todistamisen.
