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

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

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

[szerkesztés] 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ódolják, amelyek a \neg(0=0) formula egy bizonyításának Gödel-kódjait adják.)

[szerkesztés] 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 jelentettet 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 nem sokára felfedezte és igazolta a fenti, második nemteljességi tételt. November 20-án kelt levelében erről tájékoztatt 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 igé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.