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

Gödel második nemteljességi tétele Gödel első nemteljességi tételének egy lényeges kiterjesztése. Míg az első nemteljességi tétel azt mondja ki, hogy minden ellentmondásmentes elméletnek van megoldhatatlan problémája, addig ez a tétel konkrét példát mutat: minden ellentmondásmentes elméletben bizonyíthatatlan az elmélet ellentmondásmentessége.

Gödel második nemteljességi tételének elve. A Consis (T), azaz definíció szerint a ¬☐f kijelentés, valamilyen szempontból a T elmélet konzisztenciáját, ellentmondásmentességét fejezi ki. A tétel szerint ebből következik a G Gödel-mondat, így furcsamód, ha Consis (T) levezethető, akkor T csak ellentmondásos lehet.

A tétel állítása

Minden elsőrendű T elméletben eldönthetetlen Con(T) (azaz T konzisztenciája), feltéve, hogy

• T konzisztens,
• T tartalmazza a Peano-axiómarendszert és
• T elemeinek Gödel-kódjai rekurzívan felsorolható halmazt alkotnak.

(Ezek a feltételek, amelyek azonosak Gödel első nemteljességi tételének feltételeivel, már ahhoz is szükségesek, hogy egy formulával megfogalmazhassuk T konzisztenciáját. Ez azt mondja ki, hogy nincs olyan természetes szám, ami olyan természetes számok véges sorozatát kódolja, amelyek a $\neg (0=0)$ formula egy bizonyításának Gödel-kódjait adják.)

Története

1930. szeptember 5-7. között Königsbergben konferenciát tartott a Bécsi Kör és a berlini Empirikus Filozófiai Társaság Second Conference for Epistemology of the Exact Sciences címmel. Az utolsó napon, 7-én tartott kerekasztal diszkusszió során jelentette be Gödel nemteljességi tételét. Úgy tűnik, a jelenlevő között (pedig olyan nevek is köztük voltak, mint Carnap, Heyting) egyedül Neumann János fogta fel a tételt, annak mélységét és jelentőségét. A szünetben alaposan kikérdezte Gödelt, majd Berlinbe visszatérve nemsokára felfedezte és igazolta a fenti, második nemteljességi tételt. November 20-án kelt levelében erről tájékoztatta Gödelt, és véleményét kérte. Gödel válaszlevele elveszett, de Neumann november 29-iki válaszleveléből rekonstruálható, hogy Gödel elküldte cikkének különlenyomatát, aminek utolsó szakaszában szintén kimondja a második nemteljességi tételt és vázolja bizonyítását. A részletes bizonyítást cikke második részében ígéri, ez azonban soha nem jelent meg. A teljes bizonyítás először Hilbert és Bernays Grundlagen der Mathematik című könyvében jelent meg, 1939-ben.

Kapcsolódó szócikkek

• Gödel első nemteljességi tétele

További információk

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