Gödel teljességi tétele
Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye. (2023 augusztusá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ésA 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ésA 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ésHa 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ésA 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ésAz 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ésA 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ésA 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ésA tételt először Gödel igazolta doktori disszertációjában.