Keresés

Részletes keresés

Nautilus_ Creative Commons License 2011-01-28 00:19:03 85

Ezt a tételt, amelyet (67), (69), és (70)-ben nem fejeztem be (felsorolhatatlan halmazok elemeinek korlátozott meghatározása), a Metamatematika topik

 

(3795)-ös

 

hozzászólásával próbáltam meg rendesen befejezni.

 

A hozzászólás:
Nautilus_ Creative Commons License 2011-01-24 01:58:05 70

elmélet típusának egyetlen modelljének

 

helyett

"..elmélet egyetlen modelljének.."

 

Ez egyszerűen az igazság definiálási lehetetlenségének tétele: 

 

Ha G|-Q, G konzisztens elmélet, akkor nincs Fi(x), hogy G|-'Fi(Gödel(fi)<->fi', ahol minden előforduló formula típusa azonos.

 

Előzmény:
Nautilus_ Creative Commons License 2011-01-24 01:06:06 69

 

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!

 

Ha kedveled azért, ha nem azért nyomj egy lájkot a Fórumért!