Gödel első nemteljességi tétele

---

Gödel első nemteljességi tétele Kurt Gödel osztrák matematikus matematikai logika és a metamatematika nagy jelentőségű tétele, mely (a Gödel második nemteljességi tételével együtt) destruktív hatást gyakorolt a matematika formális nyelvekre építő megalapozási kísérleteire. Amellett, hogy a tételnek az analitikus nyelvfilozófiában is fontos szerepe van, bizonyításának módszere nagyban hozzájárult a rekurzív matematika (így a számítógép-tudomány) fejlődéséhez.

Gödel I. nemteljességi tételének elve. Az aritmetikában felírható az a ☐A formula, melynek jelentése: „A levezethető”, és az a G Gödel-mondat, melynek jelentése: a G mondat (tehát saját maga) nem levezethető. Ha az aritmetikából nem vezethető le ellentmondás (T ⊬ f), akkor sem G, sem negációja (¬G) nem bizonyítható, azaz G „igazságértéke” a matematika számára eldönthetetlen.

A tétel

• Tétel – Gödel első nemteljességi tétele

Minden ellentmondásmentes, a természetes számok elméletét tartalmazó, formális-axiomatikus elméletben megfogalmazható olyan állítás, mely se nem bizonyítható, se nem cáfolható.

Terminológiai megjegyzések

• 1. Formális-axiomatikus elmélet alatt bármilyen formalizált (például elsőrendű nyelvre épített) axiomatikus-deduktív elméletet érthetünk, melynek axiómarendszere rekurzívan felsorolható.
• 2. Ellentmondásos egy axiomatikus-deduktív elmélet, ha van benne olyan állítás, mely bizonyítható is és cáfolható is. Amennyiben kizárt, hogy akármelyik állítás bizonyítható és cáfolható is legyen, akkor azt mondjuk, hogy az elmélet ellentmondásmentes.
• 3. Azon, hogy tartalmazza a természetes számok elméletét, azt értjük, hogy szerepeljenek a formális nyelvben olyan kifejezések, melyek megfeleltethetők a természetes számoknak, az összeadásnak, a szorzásnak úgy, hogy a Peano-aritmetika axiómái megfogalmazhatók és egyben levezethetők is legyenek az elméletben. Ezt a feltételt még úgy is meg szokták fogalmazni, hogy az elmélet elegendően erős.
• 4. Megfogalmazható, azaz létezik a formális nyelvnek ilyen állítása. (Ez a fajta létezés ráadásul konstruktív abban az értelemben, hogy valamilyen eljárással véges lépésben kikereshető az összes állítás közül – bár a kikeresés idejére vonatkozóan nem feltétlenül lehet felső korlátot megadni.)
• 5. Bizonyítható, azaz formalizált axiomatikus-deduktív elméletek levezethetőség kritériumának megfelel.
• 6. Cáfolható egy S állítás, ha negációja (azaz a 'nem S' állítás) bizonyítható.

Megjegyzések az említett fogalmak matematikai hátteréhez

• Ha egy elméletben minden állítás bizonyítható vagy cáfolható (itt a 'vagy' a 'megengedő vagy' értelmében veendő), akkor az elméletet negációteljesnek nevezzük. Ha van olyan állítás, mely se nem bizonyítható, se nem cáfolható, akkor az elméletet nemteljesnek mondjuk, a szóban forgó bizonyíthatatlan illetve cáfolhatatlan állítások elnevezése pedig: (az axiómarendszertől) független vagy eldönthetetlen kijelentések.
• A Peano-aritmetika helyett annak egy gyengített verziója is elegendő. A tétel fennállásához a Robinson-féle Q aritmetika axiómáinak feltétele.
• Mint ismeretes, a klasszikus logikában (a parakonzisztens logikákkal szemben) egy elmélet pontosan akkor ellentmondásmentes, ha van benne olyan állítás, mely nem levezethető (ez az ellentmondásmentesség egy fontos jellemzése). Gödel első nemteljességi tétele ezen kívül azt is állítja, hogy van olyan nem levezethető állítás, melynek negációja sem vezethető le, azaz független állítás létezése ekvivalens az ellentmondásmentességgel (feltéve, hogy az elmélet elegendően erős).

Episztemológiai vonatkozások

A tétel megfogalmazható úgy is, hogy Minden elég erős, ellentmondásmentes elméletben van olyan állítás, mely eldönthetetlen, miközben igaz. Itt az igaz minősítést abban az értelemben használják, ahogy Arisztotelész, azaz úgy gondolják, minden kijelentés vagy igaz, vagy hamis. Ha elfogadjuk, hogy a kijelentés igazságértéke felderítésének lényegében egyedüli útja az, hogy találunk-e hozzájuk levezetést, akkor súlyos episztemológiai állítással kerülünk szembe. Eszerint minden elég erős elméletben lesz olyan állítás, melynek igazságáról nem fogunk tudni meggyőződni, vagyis egyik (elég erős) formális-axiomatikus rendszer sem lesz képes arra, hogy maradéktalanul minden eldöntendő kérdésre válaszoljon. Eszerint tehát eleve lehetetlen minden állítás igazságát levezetéssel megállapítani, azaz a formális rendszerek inkompetensek az összes kijelentés igazságának eldöntése dolgában.

Konkrét állítások

A nemteljességi tétel bizonyítása ad egy konkrét zárt formulát, ami az adott rendszerben eldönthetetlen. Hosszú ideig nyitott kérdés volt, hogy például a Peano-axiómarendszer esetén így igazolható-e bármilyen matematikailag érdekes állítás eldönthetetlensége. Ez először Jeff Parisnak és Leo Harringtonnak sikerült 1977-ben, akik bebizonyították, hogy a Ramsey-tétel következő általánosítása bizonyítható ZFC-ben de eldönthetetlen a Peano-axiómarendszerben:

Ha k, r, n természetes számok, akkor van olyan természetes szám N, hogy a következő állítás igaz: ha az 1,2,..,N számok n elemű részhalmazait r színnel színezzük, akkor van $a_{1}<a_{2}<\cdots <a_{s}$ sorozat, aminek minden n elemű részhalmaza ugyanazt a színt kapja és $s\geq k,a_{1}$ teljesül.

Tehát Ramsey tételét úgy módosítjuk, hogy a homogén halmaz méretének nemcsak egy előírt számot, de a saját első eleme által megadott számot is el kell érnie. Ez erősebb a véges Ramsey tételnél és gyengébb a végtelen Ramsey tételnél.

Egy másik állítás, ami megfogalmazható, de nem bizonyítható a Peano-axiómarendszerben, Goodstein tétele, ahogy azt Laurence Kirby és Jeff Paris igazolta.

Kapcsolódó szócikkek

• Gödel teljességi tétele
• Gödel második nemteljességi tétele

Források

• Raymond Smullyan: Gödel nemteljességi tételei (Typotex, 1999)

További információk

• A simple proof of a version of the Paris-Harrington Theorem
• Molnár Zoltán Gábor: Gödel nemteljességi tételei: értelmezések és félreértések (magyar nyelven). Érintő (Bolyai János Matematikai Társulat), 2017. június 1.