Epätäydellisyys

Kuuluisia Gödelin epätäydellisyyslauseita on kaksi. Ensimmäinen koskee formaalin todistuksen ja "totuuden" suhdetta ja toinen koskee konsistenssin ja epäkonsistenssin todistettavuutta. Käsittelen tässä lähinnä ensimmäistä, mutta mainitsen myös toisen.

Jotta Gödelin lause voidaan ymmärtää, pitää ensin määritellä ns Gödel-numerointi. Oletetaan että meillä on ensimmäisen kertaluvun kieli, siis ensimmäisen kertaluvun predikaattilogiikka ja sillä esitetyt kaavat. Oletamme tässä yksinkertaisuuden vuoksi että käytössämme on yhtäsuuruus (=) ja funktiosymbolit "+", "*" ja "s", missä "s(x)" tarkoittaa samaa kuin "x:stä seuraava".  Lisäksi voimme kvantifioida muuttujia - muuttujat ovat kotoisin numeroituvasta joukosta, esimerkiksi x, x', x'', jne. Vakioita on yksi, "a", ja sen tulkinta fiksataan niin, että se on tutummin nolla.

Gödel-numerointi tarkoittaa sitä, että annamme jokaiselle logiikan kielessä esiintyvälle symbolille - muuttujille, vakioille, funktiosymboleille, kvanttoreille, sulkumerkeille ja välimerkeillä - oman numeron. Varaamme lisäksi numeroita erilaisille yhdistelmämerkeille; voimme tehdä tämän "helposti" koska numeroitahan on äärettömästi. Täytyy vain pitää tarkkaan huolta, että jokaisella luvulla on yksikäsitteinen tulkinta.

En aio esittää varsinaista Gödel-numerointia tässä, mutta numerointi voidaan tehdä siten, että jokaiselle syntaktisesti oikein kirjoitetulle kaavalle, tai kaavojen sekvenssille saadaan uniikki luku, jonka tulkinta on yksikäsitteinen.  Yksi mahdollinen numerointi löytyy Wikipedian artikkelista.

Lisäksi otamme lähtökohdaksi jonkin täydellisen 1-kertaluvun päättelyjärjestelmän. Esimerkki tällaisesta on vaikkapa Hilbertin järjestelmä. Ei ole olennaista, mikä tällainen järkestelmä on, kunhan se on täydellinen - eli jokainen tautologia predikaattilogiikassa voidaan sillä todistaa - ja äärellinen. Tällaisen järjestelmän säännöille voidaan siten antaa omat numeronsa, ja voimme näiden numeroiden avulla määritellä relaatio R(x,y) joka pätee tasan silloin kun x koodaa jonkin päättelyn niin, että y on laillinen seuraava askel tässä päättelyssä. Tällä tavoin saamme itseasiassa relaation joka sanoo, että luku y koodaa tietyn väittämän logiikassa ja x koodaa sen todistuksen, käyttäen pelkästään alkeellista aritmetiikkaa.


Voimme tunnistaa tällä järjestelmällä mielivaltaisen kaavan F joka on laillisesti kirjoitettu ja jossa on yksi vapaa muuttuja; vapaa muuttuja on osa kaavaa. joten jos annamme sille jonkin tietyn arvon, esimerkiksi 5, niin saamme toisen kaavan, F(5). Kaavan itsensä numeroa merkitsemme vaikkapa #F, ja tietysti #F on eri numero kuin #F(5).

Nyt predikaattio  R(n,#F(5)) on tosi tasan silloin kun n on koodaus F(5):n todistukselle. Tarkastellaan väittämää R(n,#(F(#F)), joka sanoo, että n on koodaus sille todistukselle, joka todistaa että F(#F) pätee. Jokaisella tällaisella kaavalla on myös hyvinmääritelty yksikäsitteinen Gödel-numero.

Tämän jälkeen tarkastellaan kaavaa P(#F) joka sanoo että "Ei ole olemassa x:ää niin että R(x, #(F(#F))". pahoittelen loogisten symbolien puutetta, mutta ne on työlästä lisätä. Joka tapauksessa, koska tällekin kaavalle on Gödel-numerointi, se on ihan hyvin määritelty kaava.

Ja nyt se kikka: Mikä onkaan P(#P):n totuusarvo? Se nimittääin sanoo, että ei löydy x:ää niin, että R(x,#P(#P)) pitäisi paikkaansa. Tämä tarkoittaisi siis, että ei ole olemassa sellaista numeroa, joka koodaisi P(#P):n todistuksen.

Tämä predikaatti on aivan hyvinmääritelty. Se on väittämä joka joko pitää paikkansa tai sitten ei pidä. Jos se ei pidä paikkaansa, niin luonnollisista luvuista löytyisi sellainen alkio joka koodaisi väittämän todistuksen. Tiedämme kuitenkin, että esimerkiksi Hilbertin järjestelmä (tai mikä ikinä äärellinen päättelyjärjestelmä meillä onkaan käytössä) voi todistaa vain tosia väittämiä. Joten väittämälle ei voi olla todistusta.

Gödelin - ja kanoninen tulkinta ylipäänsä - tälle lauseelle on, että on olemassa aritmeettisia "totuuksia" joita ei voi todistaa. Tämä on todistusteoreettinen tulos; me emme voi todistaa että P(#P) on tosi kaikissa aritmetiikan malleissa. Se on selvästi tosi siinä mallissa jonka me yleensä ymmärrämme luonnollisiksi luvuiksi, ja joista Gödel-numerotkin olemme poimineet. Sensijaan se ei ole tosi kaikissa malleissa. Jos se nimittäin olisi tosi kaikissa malleissa, niin se olisi tautologia, ja me tiedämme, että kaikki tautologiat voidaan todistaa. On siis mahdollista luoda aritmetiikkajärjestelmä, jossa tämä väittämä on todistettavissa. Se on kuitenkin erilainen kuin se, jonka ominaisuuksiin nojaamme kun esitämme tämän todistuksen.

Tietojenkäsittelyllinen näkökulma ensimmäiseen epätäydellisyyslauseeseen on, että ei voida esittää sellaista algoritmia, joka tulostaisi ulos paikkansapitäviä aritmeettisiä väittämiä niin, että jokainen tosi väittämä tulee lopulta ulos, mutta ei yhtään epätotta väittämää. Tämä näkökulma tarjoaa lyhyemmän ja - joidenkin mielestä - ymmärrettävämmän tuloksen: Jokaiselle syntaktisesti erilaiselle kaavalle voidaan antaa numero, ja tästä johdetaan muutamalla tempulla ns. Berryn paradoksi. Berryn paradoksi menee jotenkin niin, että postuloidaan "Pienin luonnollinen luku, jota ei voi määritellä alle 11 sanalla", mikä itsessään on määritelmä joka on ristiriidassa itsensä kanssa; tietokoneohjelmasta joka tuottaa kaikki aritmeettiset totuudet, saadaan johdettua samantapainen paradoksi.

Toinen epätäydellisyyslause on samansukuinen, mutta siinä puhutaan aksioomajärjestelmän konsistenssista. Konsistenssilla tarkoitetaan sitä, että aksiomien joukosta ei voida löytää ristiriitoja, eli ei voida yhtä aikaa todistaa jotakin väittämää ja sen negaatiota. Gödel rakentaa tämän tuloksen samaan tapaan kuin ensimmäisen epätäydellisyyslauseenkin, mutta tämän lisäksi tarvitaan hyvin monimutkainen konstruktio jolla ilmaistaan konsistenssiväittämä. Konsistenssiväittämä on jotakuinkin se että "Ei ole olemassa toditusta epätodelle väittämälle". Konsistenssiväittämän todistus itsessään johtaa tilanteeseen, jossa samalla todistetaan ristiriita.