Gēdela numerācija definīcija un nozīme formālajā skaitļu teorijā
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.
Definīcija
Ņemot vērā saskaitāmu kopu S, Gēdela numerācija ir injektīvā funkcija.
f : S → N {\displaystyle f:S\to \mathbb {N} } 
gan ar f, gan ar f - 1{\displaystyle f^{-1}} 
(f apgrieztā vērtība) ir aprēķināmas funkcijas.
Piemēri
Bāzes notācija un virknes
Viena no vienkāršākajām Gēdela numerācijas shēmām tiek izmantota katru dienu: Atbilstība starp veseliem skaitļiem un to attēlojumiem kā simbolu virknēm. Piemēram, secību 2 3 pēc noteikta noteikumu kopuma saprot kā skaitli divdesmit trīs. Līdzīgi simbolu virknes no kāda N simbolu alfabēta var kodēt, identificējot katru simbolu ar skaitli no 0 līdz N un nolasot virkni kā veselā skaitļa N+1 bāzes N+1 atveidojumu.
Jautājumi un atbildes
J: Kas ir Gēdela skaitlis?
A: Gēdela numerācija ir funkcija, kas katram formālās valodas simbolam un formulai piešķir unikālu dabisko skaitli, ko sauc par Gēdela skaitli (GN).
J: Kas pirmais izmantoja Gēdela numerācijas jēdzienu?
A: Kurts Gēdelis pirmais izmantoja Gēdela numerācijas koncepciju, lai pierādītu savu nepilnības teorēmu.
J: Kā mēs varam interpretēt Gēdela numerāciju?
A: Mēs varam interpretēt Gēdela numerāciju kā kodējumu, kurā katram matemātiskās notācijas simbolam ir piešķirts skaitlis, un dabisko skaitļu plūsma var pārstāvēt kādu formu vai funkciju.
J: Kā mēs saucam dabiskos skaitļus, kas piešķirti ar Gēdela numerāciju?
A: Dabiskos skaitļus, kas piešķirti ar Gēdela numerāciju, sauc par Gēdela skaitļiem vai efektīvajiem skaitļiem.
J: Ko nosaka Rodžersa ekvivalences teorēma?
A: Rodžersa ekvivalences teorēma nosaka kritērijus, pēc kuriem aprēķināmo funkciju kopas numerācijas ir Gēdela numerācijas.
J: Ko attēlo Gēdela skaitļu plūsma?
A: Aprēķināmo funkciju kopas numerāciju var attēlot ar Gēdela skaitļu plūsmu.
J: Kāpēc Gēdela numerācija ir svarīga formālajā skaitļu teorijā?
O: Gēdela numerācija ir svarīga formālajā skaitļu teorijā, jo tā nodrošina veidu, kā matemātiskās formulas un funkcijas attēlot kā naturālos skaitļus, kas ļauj pierādīt tādas svarīgas teorēmas kā nepilnības teorēmu.
