Gödel első nemteljességi tétele

A Wikipédiából, a szabad lexikonból.

Gödel első nemteljességi tétele a matematikai logika és a metamatematika nagy jelentősségű tétele, mely (a második nemteljességi tétellel 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.

[szerkesztés] 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 mondat, mely se nem bizonyítható, se nem cáfolható.

[szerkesztés] 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 mondat, mely bizonyítható is és cáfolható is. Amennyiben kizárt hogy akármelyik mondat 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 mondata. (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 mondat 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 mondat, ha negációja (azaz a 'nem S' mondat) bizonyítható.

[szerkesztés] Megjegyzések az említett fogalmak matematikai hátteréhez

1 - Ha egy elméletben minden mondat bizonyítható vagy cáfolható (itt a 'vagy' a 'megengedő vagy' értelmében veendő), akkor az elméletet negációteljesnek nevezzük. Ha olyan mondat, mely se nem bizonyítható, se nem cáfolható, akkor az elméletet nemteljesnek mondjuk, a szóban forgó bizonyíthatatlan illetve cáfolhatatlan mondatok elnevezése pedig: (az axiómarendszertől) független vagy eldönthetetlen kijelentések.

2 - 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.

3 - Mint ismeretes, a klasszikus logikában (a pszeudokonzisztens logikákkal szemben) egy elmélet pontosan akkor ellentmondásmenetes, ha van benne olyan mondat, mely nem levezethető (ez az ellentmondásmenetesség egy fontos jellemzése). Gödel első nemteljességi tétel ezen kívül azt is állítja, hogy van olyan nem levezethető mondat, melynek negációja sem vezethető le, azaz független mondat létezése ekvivalens az ellentmondásmentességgel (feltéve, hogy az elmélet elegendően erős).

[szerkesztés] Episztemológiai vonatkozások

A tétel megfogalmazható úgy is, hogy

Minden elég erős, ellentmondásmentes elméletben van olyan mondat, 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 mondatok 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 mondat, 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. Sőt, nem arról van szó, hogy most még nincsenek meg a válaszaink, de ha elég sokat várunk, akkor valamelyik tudós csak megtalálja a helyes eredményt, hanem hogy elvileg kizárt, hogy bármikor is minden mondat igazságát levezetéssel megállapítsuk. A formális rendszerek tehát inkompetensek az összes kijelentés igazságának eldöntése dolgában.