Vita:Gödel teljességi tétele

Ez a szócikk témája miatt a matematikai műhely érdeklődési körébe tartozik.
Bátran kapcsolódj be a szerkesztésébe! Besorolatlan Ezt a szócikket még nem sorolták be a kidolgozottsági skálán. Nem értékelt Ezt a szócikket még nem értékelték a műhely fontossági skáláján. Értékelő szerkesztő: ismeretlen

Ebből egy szót sem értek. Nem azt mondja ki a tétel, hogy ha egy T elsőrendű elmélet konzisztens (=ellentmondásmentes), akkor van modellje?Kope 2007. május 16., 20:01 (CEST)

Rengeteg alakja van, amit itt írtam, az a legközismertebb, és magasabb logikai előtanulmányok nélkül is érthető. Amit te írsz, az meg közelebb van az eredetihez (legalábbis az enwiki szerint Gödel úgy fogalmazta meg, hogy minden formula vagy cáfolható, vagy kielégíthető), bele lehet venni azt is. De a bevezetőt célszerűbb minél egyszerűbbre fogalmazni szerintem. --Tgr ^vita / IRC 2007. május 16., 20:34 (CEST)

Semmi kifogásom az ellen, hogy ez az alak, ami valóban azonos Gödel eredeti formulázásával, szerepeljen. De. Gödel nagyon pontosan megmondta (lábjegyzetben) mit ért igazon és a tétel kimondása után, hogy mit ért bizonyításon. Ezek nem közismert fogalmak, nem ártana itt elmondani. Egyáltalán, matematikai tételt precízen kell kimondani, azaz meg kell mondani, min mit értünk. Másik megjegyzésem, egyszerűen nem értem, hogy jön a második bekezdés az elsőhöz. Mi az, ami nem igaz általában?Kope 2007. május 21., 17:57 (CEST)

Megpróbáltam átfogalmazni kicsit érthetőbbre. --Tgr^vita•IRC 2007. május 23., 01:08 (CEST)

Még mindig van valami, amit nem értek. Vegyünk egy konkrét példát: a Peano-axiómarendszerrel mi a helyzet, igaz rá vagy nem igaz a teljesség. Nekem az az érzésem, hogy a teljes szó a teljességi tétel nevében a bizonyítási rendszer (elsőrendű levezetések) teljességére, megfelelő erősségére vonatkozik, míg a nem-teljességi tétel nevében a (PA, ZF, stb) axiómarendszerek teljességére, maximális erősségére, tehát a két szóhasználat nem összevethető.Kope 2007. május 23., 07:14 (CEST)

Nem ugyanaz (ha jól értem, nem-teljességi tétel teljességfogalma azt jelenti, hogy S vagy nem S mindig bizonyítható, a teljességi tétel teljességfogalma viszont megengedi, hogy egyik se legyen az, feltéve hogy egyik sem igaz minden modellben), de kapcsolatba szokták hozni a kettőt azon az alapon, hogy Gödel módszerével konstruálhatunk egy olyan formulát, aminek az a jelentése, hogy "nem vagyok bizonyítható ebben a rendszerben". (Nem tudom, mennyire precíz ez az értelmezés, pl. Penrose használta az erős MI körüli vitában.) Ez már a teljességi tétel értelmében vett nemteljesség, nem? --Tgr^vita•IRC 2007. május 23., 09:19 (CEST)

Kope, mit hajbókolsz Tgr-nek! Mond már meg neki, hogy egyszerűen butaság, amit gondol. Tgr, legalább az angol változatot olvasd el, ott egyértelműen kiderül, hogy van két teljességfogalom, amit nem szabad összekeverni (ahogy ez a szócikkben megtörténik).

• a $\vdash$ reláció adekvát $\models$-hez, ha $\Gamma \vdash \varphi$, akkor és csak akkor, ha $\Gamma \models \varphi$ (a jelölések a szokásosak),
• $\Gamma$ negációteljes, ha tetszőleges $\varphi$ mondatra $\Gamma \vdash \varphi$ és $\Gamma \vdash \neg \varphi$ közül legalább az egyik fennáll.

Ez a két fogalom keveredik.Mozo 2007. május 27., 06:57 (CEST)

És melyik fogalom melyik tételhez kapcsolódik? --Tgr^vita•IRC 2007. május 27., 21:13 (CEST)

Az adekvátság a teljességihez, a negációteljesség a nemteljességihez. Mozo 2007. május 28., 22:11 (CEST)

Én is ezt írtam az előbb (csak nem ilyen szépen :). Akkor az a butaság, hogy a nemteljességi tétel szerint a szintaktikai következményfogalom nem adekvát a szemantikaihoz? Amikor a nemteljességi tétel bizonyításához konstruálunk egy olyan formulát, ami lényegében azt mondja, hogy "nem vagyok bizonyítható", és belátjuk, hogy tényleg nem bizonyítható, tehát igaz, akkor nem pont a két következményfogalom különböző erősségét láttuk be? --Tgr^vita•IRC 2007. május 29., 19:27 (CEST)

Áhá! Már majdnem értem mi nem világos a számodra. A kérdés, hogy milyen értelmeben gondolunk az "igaz" kitételre. A bizonyíthatóság világosan definiált fogalom. Az igazságot viszont igaziból nem nagyon találod meg a modellelmélet könyvekben, mert az inkább filozófiai logikai fogalom. Kétféle értelmezése szokott előfordulni (meg egy harmadik, egyszerű).

Az egyik Hilbert iskolája, ami érdekes módon pont hogy a Tarski fél hagyományt őrző mainstream modellemélet igazságfogalma. Ha ${\mathcal {L}}$ egy elsőrendű nyelv és ${\mathfrak {M}}$ ennek modellje, akkor az, hogy a $\varphi$ mondat igaz, úgy értendő, hogy $\varphi$ igaz ${\mathfrak {M}}$-ben, azaz ${\mathfrak {M}}\models \varphi$. Belátható, hogy ha $\varphi$ valóban mondat, azaz nem szerepel benne szabad változó, akkor vagy ${\mathfrak {M}}\models \varphi$, vagy ${\mathfrak {M}}\models \neg \varphi$. Ez az a követelemény, ami egy érvényességfogalmat igazságfogalommá tesz. Fontos azonban megjegyezni, hogy ${\mathfrak {M}}\models ...$ igazságfogalom, de $\Gamma \models ...$ nem(!), mert ez -- a teljességi tétel értelmében -- ekvivalens a $\Gamma \vdash ...$ relációval, ami triviálisan (általában) nem negációteljes. Fogalmazhatunk úgy, hogy $\Gamma \models \varphi$, tehát $\varphi$ szemantikai következménye $\Gamma$-nak, de úgy nem, hogy $\varphi$ igaz $\Gamma$-ban. Így nem mondhatod, hogy ha a G önreferenciális mondat igaz PA-ban, akkor $PA\models G$.

A másik Tarski eredeti igazságfogalma, ami a metanyelv és tárgynyelv közötti fordítás fogalmát feltételezi. Ekkor nincs szükség a modellbeli igazságra. Ellenben van egy $\mathbf {Pr} (\Gamma )$ mondatosztály, mely a levezethető mondatok osztálya és a $\mathbf {Ver} (\Gamma )$ mondatosztály, melyet Tarski eljárásával definiálhatunk és mely az igaz mondatok osztálya. Ekkor általában $\mathbf {Pr} (\Gamma )\varsubsetneqq \mathbf {Ver} (\Gamma )$ és itt is igaz, hogy egy mondat vagy igaz, vagy negációja igaz (azaz a $\mathbf {Ver} (\Gamma )$ osztály negációteljes), ahogy azt el is várjuk.

Egy harmadik értelmezés Gödel "platonista" igazságfelfogása. Eszerint szükségtelen definiálni, hogy mi az igaz mondat. Egyszerűen tudjuk, hogy minden mondat vagy igaz, vagy hamis, így a nemteljességi tételben szereplő G önreferenciális mondat vagy igaz, vagy hamis.

Tehát.

Teljességi tétel: $\Gamma \vdash ...$ adekvát $\Gamma \models ...$-hoz. Ez bizonyított, nincs kivétel alóla! (Igaziból teljességi tételnek a matematikai logikusok tényleg csak azt szokták nevezni, hogy ha $\Gamma \models ...$, akkor $\Gamma \vdash ...$. A másik irányt igazságtételnek nevezik, de itt nem arról van szó, hogy $\Gamma \models ...$ lenne az igaznak lenni reláció, csak ${\mathfrak {M}}\models ...$ az igaznak lenni reláció, sőt igaziból csak a ${\mathfrak {M}}\models ...[a]$ reláció, ahol [a] jelenti, hogy az a értékelés a ... formulához az 'i' jelet rendeli).

Nemteljességi tétel. Tudjuk, hogy a $\Gamma \vdash ...$ definíciója miatt ez a reláció nem feltétlenül negációteljes. A nem(negáció)teljességi tétel arra ad elégséges kritériumot, hogy mikor biztosan nem negációteljes $\Gamma \vdash ...$. Például akkor biztosan nem negációteljes, ha $\Gamma$ rekurzív, tartalmazza PA-t és ellentmondásmentes. Ha bármelyik nem teljesül, akkor lehethogy mégis negációteljes lesz $\Gamma \vdash ...$ (például, ha kibővítjük PA axiómarendszerét egy PA' maximális, ellentmondásmentes elméletté, akkor PA' nem marad rekurzív és negációteljessé is válik, szemben a Gödel-tétel azon naiv interpretációival, miszerint PA minden ellentmondásmentes bővítése nem negációteljes).

Röviden (ha erőltetni akarod $\models$ használatát)$\Gamma \vdash ...$ adekvát $\Gamma \models ...$-hoz, de bizonyos speciális esetekben egyértelműen kimutatható, hogy $\Gamma \vdash ...$ nem adekvát egyik fenti "igaz, hogy ..."-hoz sem, amit Kope úgy mondott, hogy a két teljességfogalom (mint a megfogalmazásból látható) nem összehasonlítható. Mozo 2007. május 30., 07:53 (CEST)