Kedves János!
Elnézést a késlekedésért. Nincs mentségem. Vannak könnyebb kérdések és vannak nehezebbek.
1. A kórt hivatkozások: Lanric Kirby fis JeíT Parii, 'Acceskíble Indepen-dence Results fór Peano Arithmetie', Buli nf London Math. Soc.^ 14 (1082). 285-293. R. L. Goodstrin, :0n the rostriotocl Ordinal Thoorem1, J. of Symlolic Logic, 9 (1944), 33-41. Paris azóta írt egy könyvet, én nem ismerem, de biztos, hogy magyon jó: The Une.ertain Reasoner's Companion. Cambridge TVacts ín Theoretical Computer Science, 39.
2. A .Jcis játékos paradoxonod1' a Richárd-paradoxon,
3. A Berry- és hazng-paradoxon szerepéről Gödéi azt mondja: ^Bármely episztemológiai antinómia felhasználható eldönthetetlen állítások léte
zésének bizonyítására." Mindkét paradoxon ilyen jellegű “feloldása" azon alapul, hogy az aritmetika mondatainak (pl. a PA rendszerben) bizonyíthatókra és cáfoltatokra való felosztásában vannak, az igaz és a hamis megkülönböztetésben viszont nincsenek vrésekv.4. Hilbert híres szabálya egy félig-formális rendszer végtelen sok premisszás következtetési szabálya. Hogy mit. jelenthet, az, hogy az f(tf) formnk minden vinstanciájah' (.F(O), -F(l), dots, f(n), dots) finit módszerekkel
bizonyítható, arról valószínűleg soha senkinek nőm volt prooíz elképzelése. (Gondolhatunk valami komplikált, nem az indukción alapuló bizonyítás-sómára - az általános vordiet, azonban az, hogy ollóié következtetési szabály ..emberi fogyasztásra alkalmatlan'1).5* “Ha megtiltanánk az önrefioxiós definíciókat, akkor nagyon kevés maradna meg a matematikából.'1
Nőm mondtam. Ügy gondolom, mog kellene különböztetni az erős és a gyenge .,önreflexiós trükköt", fi) A Clödol-számozás alapján alkalmazhatunk egy predikátumot önmagára (önmaga kódjára), ez (és rokonai) lenne az erős értelmezés. (2) Ügy tűnik azonban, mintha inkább valami másról, a predikativitás (vagy imp-rfdikativitás) fogalmáról Ifnne szó, Impredikatívnak mondunk például egy definíciót, amennyiben benne olyan kvartífikáció S7erepel, amelynek tárgyalási univerzumában a dofmiálímdó objektumok is benne vannak, aza? olvan kötött változók szerepelnek, amelvek lehetséges értékei• ^' t í L,1 O
l
között a defini
endum is előfordulhat, Vagy: akkor predikatív egy halmaz definíciója, ha az őt definiáló formula jelentése nem függ attól a feltevőstül, hogy a. szóban forgó halmaz létezik-e vagy sem, (Nino^n bevett, minden lei által elfogadott, precíz értelmezés.) A természetes számok Fregofcle definíciója pfildai.il impredikatív; ha a természetes számokat a Peano-axiómákkal vélnénk “d^fiftiáJhatónak1', akkor az indukciós axióma (minden olyan természfitfis számokból álló halmazra, amelynek a 0 eleme, és amelvnek valamennví elemével eevütt a rákö-l ll1 V1 Öl1
vetkezője is eleme, stb) miatt megint csak ez a helyzet. Persze ha a számokat eleve egy
Utaza (bármit jelentsen is ez), absztrakt univerzum elemeinek gondoljuk, akkor ez nem probléma: a Peano-axiömák ekkor csupán leírják) nem pedig definiálják a szóban forgó struktúrát. Másrészt, a természetes számok impredikativitása is kiküszöbölhető a véges halmazok bizonyos axiómarendszőreiből kiindulva* (Ez viszonylag újabb keletű eredmény.) Az “erős önreflexiói trükk'1 alkalmazásai fókfint a logika területére korlátozódnak, az impredikatív definíciók azonban a matematika más területein is megjelennek (például a felső határ axiómájában, az analízis egyik alapfeltevésében). Weyl szerint az (impredikatív, klasszikus) analízis “homokra építfitt ház a, logikus páradiCsornában". De áll.6, A Paris-Kirby tételben a szóban forgó állítást kódoló állítás szerepelhet csak, de nem azért, mert valamiféle önreferenciális trükk lenne. Az el
sőrendű PriAno-arit.mfit.iLi, nyolvóhon m£g a hatványozás som szoropol, a hatványozás explicit definíciója már eleve a szintaxis aiitmetizálásán alapul. A tótól ózon fölül bizonyos szám-sorozatokra mond ki valamit, s e7ek megint csak egy Gödéi-számozás alapján kerülhetnek be a tárgynyolvbo. A példa novozetessógo, hogy az első valódi, könnyen megragadható, ariimetikai tartalmú eldönthetetlen állítást mutatja be; korábban az ismert konkrét (tehát nem az eredeti gödeli módszerrel megkapott) eldönthetetlen állítások mind kombinatorikai jellegű problémáit (aritmetizált “fordításai") voltak. De e? semmiképpen nem jelenti, hogy az eredeti Gödel-mondat nem aritmetikai állítás - az, méghozzá olyan, amely többváltozós diofantikns egyenletek bizonyos paraméterek értékeitől függő megoldhatóságát mondja ki: ,.A szóban forgó diofantikns problémák a következőképpen jellemezhetők: Legyen P(xi>dnts>xn.yi)dofs. ym] n + m ^Itozós, ogósz együtthatós polinom; tekintsük &z Xi változókat ismeretleneknek, az y-ket pedig páramé-tereknek; a kérdés ezek után így szólt van-e a P — 0 egyenletnek a paraméterek tetszőleges egész értéke esetén megoldása az egész számok köréhen, vagy va.nnak-f a paramétereknek olya.ii értékei, amelyek mellett a? egyenlet nem oldható meg? 4 halmazelméleti axiómá,k mindegyikéhez megadható egy fonti típusú polinom, amelyre vonatkozóan a megoldhatóság kérdése éppen az illető axióma alapján válik eldönthetővé. Mindig elérhető továbbá, hogy az illető polinom fokszáma ne legyen 4-nél nagyobb,1' (Gödéi)
Budapest. 2001. 03. 2$.
ÜdvóVlettel: Csaba Foreno