Gödlovo število
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.
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.
