Gödelin epätäydellisyysteoreemit on nimi kahdelle teoreemalle (todellisille matemaattisille lauseille), jotka Kurt Gödel todisti vuonna 1931. Ne kuuluvat matemaattisen logiikan alaan ja koskettavat formaalisten aksioomajärjestelmien rajoja.

Ennen Gödelin tulosta monet matemaatikot uskoivat, että kaikki matemaattiset totuudet voisi periaatteessa johtaa jostakin täydellisestä ja ristiriidattomasta aksioomajoukosta. Järjestelmää, jolla on tämä ominaisuus, kutsutaan täydelliseksi. Järjestelmää, jossa ei ole ristiriitoja (eli ei voida johdonmukaisesti johtaa sekä väitettä että sen kieltävää väitettä), kutsutaan johdonmukaiseksi. Tällaiset formaalit järjestelmät perustuvat yleensä aksioomajoukkoihin, eli perusväitteisiin, joita ei itse tarvitse todistaa.

  1. Aina tulee olemaan kysymyksiä, joihin ei voida vastata käyttämällä tiettyjä aksioomia;
  2. Et voi todistaa, että aksioomajärjestelmä on johdonmukainen, ellet käytä erilaista aksioomien joukkoa.

Nämä lauseet tarkoittavat käytännössä sitä, että ei ole mahdollista rakentaa yhtä täydellistä ja samalla todistettavasti ristiriidatonta formaalista järjestelmää, joka sisältää tarpeeksi aritmetiikkaa. Alla selitetään tarkemmin, mitä tämä tarkoittaa, millä oletuksilla teoreemat pätevät ja miksi ne ovat merkittäviä.

Mitkä järjestelmät kuuluvat Gödelin teoreemien piiriin?

  • Oletuksena on, että järjestelmä on tarpeeksi voimakas ilmaisemaan perusaritmetiikkaa (esimerkiksi luonnollisten lukujen laskutoimitukset ja yksinkertaiset lauseet niistä). Tyypillisiä esimerkkejä ovat Peanon aritmetiikka (PA) ja monet settiopilliset järjestelmät (esim. ZF).
  • Järjestelmän aksioomajoukko on tehokkaasti esitettävissä eli rekursiivisesti lueteltavissa (eli teoriassa kone voi listata kaikki aksioomat).
  • Oletetaan, että järjestelmä on johdonmukainen (eli se ei tuota ristiriitaa). Gödelin ensimmäinen teoreema kertoo, mitä tästä seuraa.

Ensimmäinen epätäydellisyyslauseen idea

Gödel loi menetelmän, jolla formaalinen järjestelmä "voi puhua" sen omasta syntaksista ja todistuksista käyttämällä koodausta, jota kutsutaan Gödelin numeroinniksi. Jokainen symboli, lause ja todistus voidaan koodata luonnolliseksi luvuksi. Tämän avulla konstruktoidaan eräs erikoislause G, joka kuuluu suunnilleen muotoon:

"Tätä lausetta ei ole mahdollista todistaa tässä aksioomajärjestelmässä."

Jos järjestelmä on johdonmukainen, sitä ei voi todistaa (muussa tapauksessa se johtaisi ristiriitaan). Siten G on esimerkki lausunnosta, joka on tosi (järjestelmän näkökulmasta) mutta jota järjestelmä ei todista: järjestelmä on siis epätäydellinen.

Tarkemmin: jos järjestelmä voisi todistaa G:n, siitä seuraisi ristiriita (koska G väittää olevansa todistamaton), ja jos järjestelmä olisi johdonmukainen, se ei voi todistaa G:tä. Näin ollen on olemassa lause, joka on — jos järjestelmä on johdonmukainen — tosi mutta ei todistettavissa järjestelmän sisällä.

Toinen epätäydellisyyslause

Toinen teoreema sanoo, että samanlaiset järjestelmät eivät voi todistaa omaa johdonmukaisuuttaan (olettaen, että ne todella kuvaavat tarpeeksi aritmetiikkaa ja ovat johdonmukaisia). Muodollisesti: jos järjestelmä pystyy esittämään väitteen "tämä järjestelmä on johdonmukainen" ja se on itse johdonmukainen, niin se ei voi todistaa tätä väitettä.

Toisen teoreeman käytännön merkitys on, että ei voi antaa täysin sisäistä ja yksinkertaista todistusta aksioomajärjestelmän ristiriidattomuudesta ilman siirtymistä vahvempaan — eli lisääviä oletuksia sisältävään — järjestelmään.

Todistuksen teknisiä elementtejä (lyhyesti)

  • Gödelin numerointi: symbolit ja lauseet koodataan luvuiksi niin, että syntaktinen käsittely on aritmeettista laskentaa.
  • Representoitavuus: lauseiden ja todistusten ominaisuudet voidaan ilmaista aritmeettisina lauseina.
  • Diagonalisaatio/itseviittaus: muodostetaan lause joka viittaa omaan numerokoodiin ja ilmaisee, ettei sille ole todisteita.
  • Rosserin parannus: myöhemmin Rosser kehitti vahvemman version, joka vaatii heikompia oletuksia johdonmukaisuuden osalta.

Merkitys ja vaikutus matematiikkaan ja filosofialle

Gödelin teoreemat muuttivat käsitystä matematiikan perustasta ja vaikuttivat laajasti:

  • Ne päättivät käytännössä Hilbertin ohjelman tavoitteet: ei ole mahdollista täydellisesti ja täysin sisäisesti perustella koko matematiikkaa yhden, kaikkien totuuksien kattavan aksioomajoukon avulla.
  • Ne yhdistyvät Turingin ja Churchin työihin muodostaen osan laskettavuuden ja päätettävyyden teoriaa: Gödelin lauseet liittyvät käsitteisiin, kuten päätettämättömyyteen ja pysäyttämisongelmaan.
  • Ne synnyttivät käsityksiä matemaattisesta totuudesta vs. todistettavuudesta: lause voi olla "tosi" (esim. intuitiivisessa aritmeettisessa mielessä) mutta olla todistamaton annetussa formaalijärjestelmässä.
  • Ne johtivat laajemmalle tutkimukselle riippumattomuuksista: monia matemaattisia väitteitä (esimerkiksi eri muodoissaan kontinuumihypoteesi) voidaan näyttää riippumattomiksi tietyistä aksioomajoukoista.
  • Filosofisesti ne vaikuttavat keskusteluihin älykkyydestä, tietoisuuden ja formalisoinnin rajoista sekä matematiikan ontologiasta.

Yleisiä väärinkäsityksiä

  • Gödel ei osoittanut, että mikään matemaattinen väite olisi "väärä" tai että matematiikka olisi hyödytön — hän osoitti rajoitteen formaalijärjestelmien sisäiselle todistettavuudelle.
  • Epätäydellisyys ei koske kaikkia mahdollisia järjestelmiä: triviaalit tai liian heikot järjestelmät (joissa ei voi esittää perusaritmetiikkaa) eivät kuulu teoreeman piiriin.
  • Gödelin lauseet eivät anna suoraa menetelmää löytää yksittäisiä riippumattomia lauseita kaikissa järjestelmissä, mutta ne kertovat tällaisia lauseita aina olevan, jos järjestelmä on riittävän vahva.

Yhteenveto

Gödelin epätäydellisyysteoreemit näyttävät, että mielenkiintoisissa (ei-triviaaleissa), aritmetiikan sisältävissä ja tehokkaasti määriteltävissä formaalijärjestelmissä on väistämättä joko todistamattomia mutta tosia lauseita tai järjestelmä on ristiriitainen. Lisäksi tällainen järjestelmä ei voi osoittaa omaa johdonmukaisuuttaan ilman, että hyppää sen ulkopuolelle vahvempaan järjestelmään. Nämä tulokset ovat perusta monille nykyaikaisille tutkimusaloille logiikassa, tietojenkäsittelytieteessä ja matemaattisessa filosofiassa.

Esimerkkejä järjestelmistä, joihin teoreemat soveltuvat: Peanon aritmetiikka (PA), Principia Mathematicaa vastaavat muodolliset järjestelmät ja monet settiopilliset järjestelmät (esim. ZF). Rosserin ja muut jatkokehitelmät tarkentavat teoreemien oletuksia ja johtopäätöksiä.