Következmény. Ha Gamma eldönti f értékkészletének komplementerét, akkor, mivel minden igazolás véges, Gamma egy véges részéből is eldönthetjük a rekurzív f értékkészletének véges sok elemét.
helyett inkább:
Következmény. Ha Gamma eldönti f értékkészletének komplementerét, akkor, mivel minden igazolás véges, Gamma egy véges részéből is eldönthetjük a rekurzív f értékkészlete komplementerének véges sok elemét (szavát).
--------------------------------------
Néhány javítás, de a tétel jó volt.
Az alábbiak továbbra is formális nyelvelmélet; generatív grammatika helyett azonban mindenhol a generáló rekurzív függvényt, szavak helyett számokat veszünk.
Az igazság definiálhatatlansági tételből következik, hogy a Gammában, nemrekurzívan, a P{Ax}-okkal megadott M-igazsághalmaz, függvény, (Gödel-számok halmaza) nem definiálható egyetlen formulával, ha maradunk az adott nyelvben. Ami azt illeti, ha van egy konzisztens elméletünk, amelyből a Q rendszer levezethető, az elmélet típusának egyetlen modelljének igazsághalmaza sem definiálható az adott típusban (itt: az epsilon nyelvben).
(RfC viszont igen.)
Még akkor sem, ha ez úgysem lenne effektív, hiszen egy Truth(Gödel(fi)) formula ekvivalenciája fi-vel mindig Gamma más és más axiómáiból, összességében nemrekurzív elméletből lenne levezetve.
Másrészt létezik F(x,y) rekurzív függvény, melynek első változójának helyettesítjük Gödel(fi)-t, ahol fi igaz, a második változó (az értékkészlet eleme) pedig csakis RfC egy eleme lehet.
Gamma sajnos képtelen igazolni, hogy F tényleg jó: ez ugyanis azt jelentené, hogy ha F(a,b) igazolható Gammában, akkor "a" egy igaz fi Gödel-száma, ami definiálná az M modell igazságát.
Ezért folyamodhatunk egy olyan elmélethez, amely TruthM-et definiálni már képes. Ez lehet egy kifejezőképesebb halmazelmélet, például a Morse-Kelley, amelyben tetszőleges ZFC-modell igazsága definiálható. MK egy tetszőleges modelljének elméletében már a rekurzív F(x,y) meghatározható, és reprezentálható (egyébként, F persze Gammában is reprezentálható - ha benne F rekurzív!). Ekkor "tudni" fogjuk (persze az MK-orákulum ismeretében), hogy melyik rekurzív átszámolási függvény lesz jó F-nek. Van ugyanis olyan formula az MK-modell elméletében, amely F-ről azt mondja, hogy "én TruthM Gödel-számait számolom át f értékkészletének komplementerébe".
DF persze nem felsorolható az MK-modell elméletében sem!
Ekkortól tehát F-et nyugodtan használhatjuk Gammában is, RfC elemeinek meghatározására, ha F rekurzív (ezt elérhetjük megfelelő MK-elmélettel): a Morse-Kelley garantálja, hogy az F értékkészletének elemei éppen a nem-felsorolható halmaz elemei lesznek.
----------------------------------
Feltehető a kérdés, hogy erre a hosszas igazolásra miért van szükség, például arra, hogy a Morse-Kelley-modell elmélete és Gamma f értékkészletének komplementere feletti degree-n van?
Azért, mert ha nem így lenne, akkor azok az akár paramétermentes másodrendű számelméleti formulák a HYP hiperaritmetikai hierarchiában, és az Analitikus Hierarchiában, amelyek számhalmazokat definiálnak, átírva halmazelméletre, olyan paramétereket tartalmaznának, amelyek "transzcendensek", matematikai módon megfogalmazva: nem-effektívek.
És az az F, amely a degree "felettre" számol, nemcsak hogy nem lesz rekurzív, hanem a definiáló halmazelméleti formulájának paraméterei szintén nem-effektívek, vagyis semmilyen módon nem számíthatók ki -
máshogyan fogalmazva: sem halmazelméleti, sem másmilyen (pl. aritmetikai) formulával nem írható le a Church-tézisen belül.
------------------------------
Végül megjegyzem, hogy Shoenfield egy tétele (1959.) szerint, MINDEN Ax axiómarendszernek van teljes kiterjesztése 0"-n, vagy alatta (élesebben kimondva: alatta).
Gondoljuk meg: a sztenderd számelmélet igazsághalmaza 0{omega}! Óriási tehát a bonyolultságbeli különbség.
Hogyan lehet ez?
Úgy, hogy Ax, ha lényegesen nemteljes is, független formuláinak halmaza 0", vagy alatti degree-n van, hiszen Sigma_1-halmaz komplementere. Vegyük ezt a halmazt, és adjuk minden formulájának igazságértéket, úgy, hogy a bonyolultságot nem növeljük, hiszen rekurzív átalakítás.
A következő módon. Ha már adtunk egy Fi formulának igazságértéket, vegyük hozzá Ax-hoz, és a következő Fi* formula, ha ellentmondásos Ax+Fi-vel, akkor legyen hamis (~Fi*), ha igaz, akkor ez persze bizonyíthatatlan.
Csakhogy használjuk 0' orákulumát, és azzal a konzisztencia-probléma eldöntjető. Ekkor Fi legyen igaz. Mivel legfeljebb 0' orákulumát használtuk, maradtunk legfeljebb 0"-nél. Q.E.D.
Felhívom a figyelmet, hogy elképesztően bonyolult Ax-teljes elméletek is vannak, még 0{omega_1CK} felett is!
|