Gödelin epätäydellisyyslause

Gödelin epätäydellisyyslauseet ovat Kurt Gödelin vuonna 1931 todistamat kaksi lausetta. Epätäydellisyyslauseen mukaan lukuteorian sisältävä aksiomaattinen järjestelmä on epätäydellinen sillä aina on tosia lauseita, joita ei voi todistaa järjestelmän sisäisillä menetelmillä^[1].

Nämä lauseet tulkitaan usein osoitukseksi siitä, että vastaus Hilbertin toiseen ongelmaan on kielteinen: ei ole olemassa "matematiikan perustaa", täydellistä ja konsistenttia aksiomaattista järjestelmää, joka yksin kattaisi kaiken matematiikan.

Gödelin ensimmäinen epätäydellisyyslause sanoo, että mikään ristiriidaton aksioomajärjestelmä T, jonka kaikki todet lauseet voidaan luetella jollakin "tehokkaalla menetelmällä" (olennaisesti: "tietokoneohjelmalla"), ei pysty todistamaan kaikkia tosiasioita luonnollisista luvuista. Siis osa järjestelmän tosista lauseista ei ole todistettavissa järjestelmän sisältä, vaan siihen vaaditaan jotain toista järjestelmää.

Eräs tällainen tosi mutta ei-todistettava lause on Gödelin lause ("G"), joka sanoo: "Lause G ei ole todistettavissa teoriassa T." Sitä lausetta ei siis voi todistaa teoriassa T, mutta on kyllä mahdollista laajentaa T toiseksi teoriaksi T', joka sisältää kaikki järjestelmän T lauseet ja enemmänkin (esimerkiksi lauseen G) ja jossa lause G on todistettava. Ensimmäisen epätäydellisyyslauseen perusteella myös järjestelmässä T' on lauseita, joita siinä itsessään ei voi todistaa (mm. sen oma Gödelin lause).

Gödelin toinen epätäydellisyyslause osoittaa, että jos jokin ristiriidaton aksioomajärjestelmä pystyy todistamaan tietyt perusasiat luonnollisista luvuista, se ei pysty todistamaan kyseisen aksioomajärjestelmän täydellisyyttä.

Epätäydellisyysteoreema on analoginen Turingin koneen pysähtymisongelman kanssa, jonka mukaan ei ole olemassa sellaista ohjelmaa (Turingin konetta) A, joka tarkastaisi toisesta ohjelmasta (Turingin koneesta) B aukottomasti, päättyykö ohjelman B suoritus koskaan. Syynä tähän on se, että jos olisi olemassa ohjelma A, joka tutkii, päättyykö B:n suoritus koskaan siten, että A(B)=1, jos B:n suoritus päättyy ja A(B)=0, muuten, niin olisi mahdollista kehittää toinen ohjelma A', joka jää ikisilmukkaan, jos A(B)=1 ja päättyy, jos A(B)=0. Nyt kuitenkin A'(A') päättyy, jos A' jää ikisilmukkaan ja ei pääty, jos A' ei jää ikisilmukkaan.

Ei ole olemassa algoritmia, jolla voitaisiin mielivaltaisesta lukuteoreettisesta kahden luonnollisen luvun funktiosta f(n,x), jonka arvo on luonnollinen luku, tarkastaa, onko olemassa luonnollista lukua N, jolle f(N,x)=0. Useissa epätäydellisyyslauseen todistuksissa luodaan teorioista Gödel-numerointi tämän kaavan luvulle x, joilla ongelma voidaan palauttaa tässä mainittuun muotoon.

• Raatikainen, Panu: Gödel's Incompleteness Theorem The Stanford Encyclopedia of Philosophy. The Metaphysics Research Lab. Stanford University. (englanniksi)