Gödel teljességi tétele

A Wikipédiából, a szabad enciklopédiából

Gödel teljességi tétele a matematikai logika fontos tétele, azt mondja ki, hogy ha egy elsőrendű elméletben egy tetszőleges mondat minden modellben igaz, akkor bizonyítható is.

Az igazság tétel[szerkesztés | forrásszöveg szerkesztése]

A tétel szerint, ha egy L elsőrendű nyelvben megadott T elméletnek (zárt formulák halmazának) van modellje, akkor konzisztens (ellentmondásmentes). Ez nyilvánvaló, hiszen a modellben minden T-ből levezethető állításnak igaznak kell lennie, márpedig a modellen nem teljesülhet egyszerre egy zárt formula és tagadása.

A teljességi tétel[szerkesztés | forrásszöveg szerkesztése]

A teljességi tétel az igazság tétel megfordítása:

Ha egy L elsőrendű nyelvben megadott T elmélet konzisztens, akkor van modellje.

A teljességi tétel másik alakja[szerkesztés | forrásszöveg szerkesztése]

Ha egy L elsőrendű nyelvben T elmélet és \varphi zárt formula, amire teljesül T\models \varphi, azaz igaz T minden modelljében, akkor T\vdash \varphi is teljesül, azaz \varphi levezethető T-ből.

Ez az állítás ekvivalens a teljességi tétel fenti alakjával. Ennek az állításnak egy interpretációja a szócikk elején levő állítás.

Példák[szerkesztés | forrásszöveg szerkesztése]

A fenti állítás szerint, ha például (csoportelméleti eszközökkel) belátjuk, hogy ha egy csoportban minden elem rendje 1 vagy 2, akkor a csoport kommutatív, akkor ez le is vezethető a csoportaxiómákból. Hasonlóan, ha belátjuk, hogy a halmazelmélet ZFC axiómarendszerének minden modelljében igaz egy állítás, akkor az az állítás bizonyítható ZFC-ből. Ez nem csak elképzelt lehetőség: a Baumgartner–Hajnal-tétel első bizonyítása úgy született, hogy a szerzők a Martin-axióma segítségével belátták, hogy az állítás igaz ZFC minden modelljében.

A teljességi tétel bizonyítása[szerkesztés | forrásszöveg szerkesztése]

Az alábbiakban a Henkin-konstansos bizonyítás vázlatát adjuk. Először feltesszük, hogy a nyelv megszámlálható. Bővítsük ki a nyelvet megszámlálható sok új konstansjellel: c_0,c_1,\dots. Soroljuk fel a kibővített nyelv zárt formuláit, mint \varphi_0,\varphi_1,\dots. Soroljuk fel a kibővített nyelv kvantorral kezdődő formuláit is: (\exists x)\psi_0(x),\dots. Elkészítjük konzisztens elméletek növő T_0\subseteq T_1\subseteq T_2\subseteq\cdots láncát a következőképpen: legyen T_0=T. Ha a konzisztens T_{2n} adott, legyen T_{2n+1}=T_{2n}\cup\{\varphi_n\} vagy T_{2n+1}=T_{2n}\cup\{\neg\varphi_n\} aszerint, hogy az első konzisztens-e vagy sem. Ha a konzisztens T_{2n+1} adott, legyen T_{2n+2}=T_{2n+1}\cup\{\exists x\psi_n(x)\to \psi_n(c_i)\} ahol c_i egy olyan konstansjel, ami nem fordul el a \psi_n formulában. T_{2n+2} még mindig konzisztens. T^*=T_0\cup T_1\cup\cdots mint konzisztens elméletek egyesítése, konzisztens és mivel minden zárt formulát vagy tagadását tartalmazza, teljes. Definiáljuk a \sim relációt a konstansjeleken a következőképpen: c_i\sim c_j, ha [c_i=c_j]\in T^*. Ez ekvivalencia-reláció, jelölje c_i ekvivalenciaosztályát [c_i]. Ekkor az ekvivalenciaosztályokra struktúrát építhetünk: ha R k-változós relációjel, R([c_{i_1}],\dots,[c_{i_k}]), ha R(c_{i_1},\dots,c_{i_k})\in T^*, hasonlóan a konstansjelekre és a függvényjelekre. Ekkor ez a struktúra modellje T-nek.

Ha a nyelv megszámlálhatónál nagyobb, hasonlóan járunk el, csak elméleteknek nem megszámlálható hosszú, hanem \kappa hosszú növő láncát készítjük el, ahol \kappa a nyelv számossága. Limesz lépésekben mindig a korábbi elméletek egyesítését kell venni. Ez még mindig konzisztens marad, mert minden bizonyítás véges lévén konzisztens elméletek növő transzfinit láncának egyesítése is konzisztens.

Következményei[szerkesztés | forrásszöveg szerkesztése]

A fenti bizonyítás nemcsak modellt, de megszámlálható modellt ad (|L| számosságút, ha az L nyelv megszámlálhatónál nagyobb). Ezért a bizonyítás adja a Löwenheim–Skolem–Tarski-tételt is, továbbá Gödel kompaktsági tételét is.

Kapcsolata a kiválasztási axiómával[szerkesztés | forrásszöveg szerkesztése]

A tétel használja a kiválasztási axiómát. Annak gyengébb változatával, az ultrafilterek létezéséről szóló állítással ekvivalens.

Története[szerkesztés | forrásszöveg szerkesztése]

A tételt először Gödel igazolta doktori disszertációjában.