Formālajā skaitļu teorijā Gēdela numerācija ir funkcija, kas katram kādas formālās valodas simbolam un formulai piešķir unikālu dabisku skaitli, ko sauc par Gēdela skaitli (GN). Šo jēdzienu pirmo reizi izmantoja Kurts Gēdelis, lai pierādītu savu nepilnības teorēmu. Gēdela numerācija ļauj izteikumus no sintakses pasaules pārnest uz aritmētikas valodu, kas padara iespējamu sintaktisku apgalvojumu atspoguļošanu kā aritmētiskas īpašības naturālajiem skaitļiem.

Konstrukcija — kā tiek kodētas formulas

Vienkāršākais un visplašāk minētais paņēmiens izmanto pirmo skaitļu faktorizāciju: katram valodas simbolam piešķir vienu unikālu kodu (dabisku skaitli), piemēram, simbolam s_i kodu c_i, un tad rindai simbolu (a1, a2, ..., an) atbilst skaitlis

GN(a1,...,an) = 2^{c_{a1}} · 3^{c_{a2}} · 5^{c_{a3}} · ...

Šādi katrai secībai (tātad arī katrai formulai vai pierakstam) tiek piešķirts viennozīmīgs dabiskā skaitļa produkts, ko var viennozīmīgi atšifrēt, izmantojot pirmskaitļu faktorizāciju. Ir arī citas pieejas (piem., pārašanas funkcijas, β-funkcijas), taču būtība ir tāda, ka kodēšanas un dekodēšanas procesiem jābūt efektīvi izsakāmiem (bieži prasa, lai tie būtu rekurzīvi vai primāri rekurzīvi).

Galvenās īpašības

  • Injektivitāte: dažādām simbolu secībām tiek piešķirti dažādi naturālie skaitļi.
  • Efektivitāte / aprēķinamība: gan kodēšana, gan dekodēšana ir aprēķināmas funkcijas (parasti primāri rekurzīvas). Tas nodrošina, ka sintaktiskās īpašības var tikt izteiktas ar aritmētiskiem predikātiem.
  • Nepieciešamība nav unikāla: Gēdela numerācija nav viennozīmīgi noteikta — ir daudz pieņemamu numerāciju, bet tās visas ir "ekvivalentas" no formālās teorijas viedokļa (maiņa starp tām ir efektīvi aprēķināma transformācija).

Loma loģikā un Gēdela teoremā

Ar Gēdela numerāciju var "ārīt" sintaktiskus jēdzienus ar skaitļu īpašībām. Piemēram, apgalvojumi kā "x ir formula", "y ir pierādījums no formulas z" vai "formulai φ ir pierādījums" var tikt pārveidoti par aritmētiskām attiecībām starp Gēdela skaitļiem. Tas ļāva Gēdelim definēt iekšējo provability predikātu sistēmā aritmētikā un pēc tam izmantot diagonāles tipu argumentu, lai uzbūvētu teikumu, kas "apgalvo, ka tas nav pierādāms" — galvenais ieguvums, no kura izriet nepilnības rezultāts.

Piemērs (vienkāršots)

Pieņemsim, ka simboliem "0", "S" (nlākums), "+", "·", "=", "(", ")" u.c. piešķiram kodus 1,2,3,4,5,6,7,... Tad piemēram formulai "S(S(0))=S(0)" atbilstošais GN varētu būt

2^{k(S)} · 3^{k(} · 5^{k(S)} · 7^{k(} · 11^{k(0)} · ... — kur k(x) ir priekšmeta x kods. Šis piemērs parāda, kā secības pozīcija tiek iemūžināta, izmantojot pirmskaitļus kā vietturiem.

Saistītie jēdzieni un rezultāti

  • Aprēķināmo funkciju kopu numerācijas attēlošanai izmanto Gēdela skaitļus; dažkārt runā par efektīvajiem skaitļiem.
  • Rodžersa ekvivalences teorēma (Rogersa ekvivalence) nosaka kritērijus, pēc kuriem aprēķināmo funkciju kopas numerācijas ir "pieņemamas" un kā tās ir ekvivalentas viena otrai. Tā nodrošina, ka būtiskie rezultāti (piem., nepilnības) nav atkarīgi no konkrētas numerācijas izvēles.
  • Daudzas mūsdienu formalizācijas lieto nedaudz attīstītākas konstrukcijas (piem., Kleenes T-predikātu, β-funkciju), tomēr visi šie paņēmieni ir būtībā Gēdela numerācijas plašākas idejas realizācija.

Kāpēc tas ir svarīgi

Gēdela numerācija ir pamatinstruments, kas ļāva magistrālajai idejai — aritmētiskai sintakses aritmetizācijai — īstenoties. Bez uzticamas un efektīvas numerācijas nebūtu iespējams formulēt iekšējas provability predikātus un veikt pašreferenci formalizētā veidā. Tādējādi Gēdela numerācija nav tikai tehnisks paņēmiens: tā ir centrāls elements skaitļu teorijas un formālās loģikas pamatos, kas saista sintaksi, aprēķināmību un patoloģiskus rezultātus kā nepilnības teoremas.