Gödel teljességi tétele

A Wikipédiából, a szabad enciklopédiából
Jump to navigation Jump to search

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]

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]

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]

Ha egy L elsőrendű nyelvben T elmélet és zárt formula, amire teljesül , azaz igaz T minden modelljében, akkor is teljesül, azaz 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]

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]

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: . Soroljuk fel a kibővített nyelv zárt formuláit, mint . Soroljuk fel a kibővített nyelv kvantorral kezdődő formuláit is: . Elkészítjük konzisztens elméletek növő láncát a következőképpen: legyen . Ha a konzisztens adott, legyen vagy aszerint, hogy az első konzisztens-e vagy sem. Ha a konzisztens adott, legyen ahol egy olyan konstansjel, ami nem fordul el a formulában. még mindig konzisztens. mint konzisztens elméletek egyesítése, konzisztens és mivel minden zárt formulát vagy tagadását tartalmazza, teljes. Definiáljuk a relációt a konstansjeleken a következőképpen: , ha . Ez ekvivalencia-reláció, jelölje ekvivalenciaosztályát . Ekkor az ekvivalenciaosztályokra struktúrát építhetünk: ha R k-változós relációjel, , ha , 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 hosszú növő láncát készítjük el, ahol 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]

A fenti bizonyítás nemcsak modellt, de megszámlálható modellt ad ( 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]

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]

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