Főmenü megnyitása

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ételSzerkeszté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ételSzerkeszté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 alakjaSzerkeszté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ákSzerkeszté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ásaSzerkeszté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ényeiSzerkeszté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ávalSzerkeszté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éneteSzerkesztés

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