Gödel teljességi tétele

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

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

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

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

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

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ítese, 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

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

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

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