Gödelovo številčenje: definicija in kodiranje formul (Gödelova števila)
V teoriji formalnih števil je Gödelovo številčenje funkcija, ki vsakemu simbolu in formuli nekega formalnega jezika dodeli edinstveno naravno število, imenovano Gödelovo število (GN). Pojem je prvič uporabil Kurt Gödel pri dokazovanju svojega teorema o nepopolnosti.
Gödelovo številčenje lahko razumemo kot kodiranje, pri katerem je vsakemu simbolu matematičnega zapisa dodeljeno število, tok naravnih števil pa lahko predstavlja neko obliko ali funkcijo. Oštevilčenje množice izračunljivih funkcij lahko nato predstavimo s tokom Gödelovih števil (imenovanih tudi efektivna števila). Rogersov izrek o enakovrednosti navaja merila, za katera oštevilčenja množice izračunljivih funkcij so Gödelova oštevilčenja.
Osnovna ideja in formalna definicija
Osnovna ideja Gödelovega številčenja je pretvoriti sintaktične objekte (simboli, formule, dokazi) v naravna števila tako, da lahko o lastnostih teh objektov razpravljamo znotraj aritmetike. Formalno je to injektivna (pogosto tudi izračunljiva) funkcija
- f : {simboli / formule / zaporedja simbolov} → N,
- pri čemer različnim simbolom/formulam pripadajo različna naravna števila.
Pomembno je, da je številčenje dovolj učinkovito (npr. rekurzivno ali celo primitivno rekurzivno), saj Gödel v dokazih potrebuje mehanizme za izračun in preverjanje lastnosti kod (npr. ali dano število predstavlja veljavno formulo ali dokaz).
Tipična metoda kodiranja (kodiranje s praštevili)
Ena najbolj znanih metod je kodiranje zaporedja simbolov s produktom praštevil. Postopek je naslednji:
- Najprej se vsakemu osnovnemu simbolu jezika dodeli celo število (npr. 0,1,2,...).
- Za zaporedje simbolov s kodami k1, k2, ..., kn se izračuna Gödelovo število kot produkt:
GN = 2^{k1+1} · 3^{k2+1} · 5^{k3+1} · ... · p_n^{kn+1},
kjer so 2,3,5,... zaporedje praštevil, eksponentom pa pogosto prištejemo 1, da se izognemo eksponentu 0 (in s tem izgubi informacije o koncu zaporedja). Takšno kodiranje je injektivno zaradi osnovnega izreka o enolični faktorizaciji: faktorji in njihovi eksponenti enolično določajo zaporedje kod.
Obstajajo tudi druge metode, npr. uporaba Cantorjevega pariščnega funkcijona za kodiranje dveh ali več števil v eno samo, ali kodiranja, ki so bolj praktična za formalne dokaze (vključujejo tudi oznake za ločnice, dolžine zapisov itd.).
Primer
Če simbolom dodelimo številčne kode npr. "("↦1, ")"↦2, "∀"↦3, "x"↦4, "P"↦5, "→"↦6) in želimo zakodirati formulo ∀x (P(x) → P(x)), prevedemo formulo v zaporedje kod in nato izračunamo produkt ustreznih praštevil z danimi eksponenti. Razbitje na praštevila nato omogoči dekodiranje nazaj v originalno zaporedje simbolov.
Lastnosti in zahteve Gödelovih številčenj
- Injektivnost: različnim simbolom oziroma formulam morajo pripadati različna naravna števila.
- Izračunljivost: preslikava iz simbola/formule v Gödelovo število in obratno naj bo izračunljiva (rekurzivna); v mnogih konstrukcijah se zahteva celo primitivna rekurzivnost.
- Enoličnost dekodiranja: iz Gödelovega števila je treba učinkovito pridobiti originalni sintaktični objekt (npr. s faktorizacijo ali parnim kodiranjem).
- Spojnost z metamatematiko: lastnosti o sintaksi (npr. "m je koda veljavne formule" ali "m kodira dokaz formule φ") je treba izraziti kot aritmetične lastnosti števil — to omogoča notranjo reprezentacijo izjav o jeziku v okviru aritmetike.
Uporaba v Gödelovem dokazu o nepopolnosti
Gödelovo številčenje je jedro njegovega pristopa: s pomočjo številčenja lahko v aritmetiki izrazimo trditve o lastnih izjavah in dokazih. Pomembna tehnika je diagonalizacija (samoreferenčnost), ki Gödelu omogoči konstrukcijo formule, ki pravi o sebi: "Ta formula ni dokazljiva." Če je sistem konsistenten in dovolj močan, ta formula ni dokazljiva v sistemu — to je bistvo prvega izreka o nepopolnosti.
Gödelova številčenja in efektivna oštevilčenja
Pri oštevilčenju množice izračunljivih funkcij ali programov je pomembno, da je oštevilčenje "efektivno" — to pomeni, da obstajajo izračunljivi postopki za prevesti med indeksom in funkcijo, ter za izračunovanje vrednosti funkcije z danim indeksom. V tem okviru se pojavlja Rogersov izrek o enakovrednosti, ki navaja kriterije, za katera oštevilčenja množice izračunljivih funkcij so "enakovredna" ali so Gödelova oštevilčenja. Rogersov izrek med drugim obravnava transformacije med različnimi oštevilčenji, ki jih dosežemo z izračunljivimi funkcijami.
Praktične in konceptualne omejitve
- Kljub temu, da je Gödelovo številčenje teoretično zelo močno, v praksi kodirana števila hitro postanejo izjemno velika in neučinkovita za človeško branje.
- Pomembna ni sama izbira konkretnega številčenja (veliko različic deluje), ampak da številčenje izpolnjuje potrebne računske pogoje (izračunljivost, enoličnost), saj to omogoči formalizacijo metamatematičnih izjav znotraj aritmetike.
Povzetek
Gödelovo številčenje je način, kako sintaktične objekte formalnega jezika preslikati v naravna števila na način, ki je izračunljiv in povratno dekodiran. To kodiranje je ključno orodje v teoriji izračunljivosti in v Gödelovih dokazih, saj omogoča, da ojska o sintaksi postanejo aritmetične trditve. Rogersov izrek daje kriterije, kdaj oštevilčenja množice izračunljivih funkcij štejejo za Gödelova oziroma efektivna oštevilčenja.
Opredelitev
Ob dani števni množici S je Gödelovo oštevilčenje injekcijska funkcija
f : S → N {\displaystyle f:S\to \mathbb {N} } 
s f in f - 1{\displaystyle f^{-1}} 
(obratna vrednost f) sta izračunljivi funkciji.
Primeri
Osnovni zapis in nizi
Ena najpreprostejših Gödelovih številskih shem se uporablja vsak dan: V tem primeru se uporabljajo naslednje Gödlove metode: skladnost med celimi števili in njihovimi predstavitvami kot nizi simbolov. Na primer, zaporedje 2 3 je po določenem sklopu pravil razumljeno kot število triindvajset. Podobno lahko niz simbolov iz neke abecede z N simboli kodiramo tako, da vsak simbol poistovetimo s številom od 0 do N in beremo niz kot osnovno N+1 predstavitev celega števila.
Vprašanja in odgovori
V: Kaj je Gödelovo oštevilčenje?
O: Gödelovo številčenje je funkcija, ki vsakemu simbolu in formuli formalnega jezika dodeli edinstveno naravno število, imenovano Gödelovo število (GN).
V: Kdo je prvi uporabil koncept Gödelovega številčenja?
O: Kurt Gödel je prvi uporabil koncept Gödelovega oštevilčenja pri dokazovanju svojega izreka o nepopolnosti.
V: Kako si lahko razlagamo Gödelovo številčenje?
O: Gödelovo številčenje lahko razlagamo kot kodiranje, kjer je vsakemu simbolu matematičnega zapisa dodeljeno število, tok naravnih števil pa lahko predstavlja neko obliko ali funkcijo.
V: Kako imenujemo naravna števila, ki so dodeljena z Gödelovim številčenjem?
O: Naravna števila, ki jih dodeli Gödelovo številčenje, se imenujejo Gödelova števila ali efektivna števila.
V: Kaj pravi Rogersov izrek o enakovrednosti?
O: Rogersov izrek o enakovrednosti navaja merila, za katera oštevilčenja množice izračunljivih funkcij so Gödelova oštevilčenja.
V: Kaj predstavlja tok Gödelovih števil?
O: Oštevilčenje množice izračunljivih funkcij je mogoče predstaviti s tokom Gödelovih števil.
V: Zakaj je Gödelovo številčenje pomembno v formalni teoriji števil?
O: Gödelovo številčenje je pomembno za formalno teorijo števil, saj omogoča predstavitev matematičnih formul in funkcij kot naravnih števil, kar omogoča dokazovanje pomembnih trditev, kot je trditev o nepopolnosti.
