Gödelin epätäydellisyyslauseet

Abstract

Ossi Kosonen, Gödelin epätäydellisyyslauseet, Gödel's incompleteness , matematiikan pro gradu -tutkielma, 57 sivua, Jyväskylän yliopisto, Matematiikan ja tilastotieteen laitos, syksy 2016. Tämän tutkielman tarkoituksena on todistaa Gödelin kaksi epätäydellisyyslausetta RA-kielessä. Itävaltalais-amerikkalainen Kurt Gödel todisti nimeänsä kantavat lauseet artikkelissaan vuonna 1931. Gödel ei itse varsinaisesti käyttänyt RA-kieltä lauseiden alkuperäisissä todistuksissa, mutta tässä tutkielmassa RA-kieli on valittu formaaliksi kieleksi, koska se perustuu predikaattikielten pohjalle. RA-kielen tarkoitus on formalisoida mahdollisimman hyvin aritmetiikka, joka käytännössä onnistuu mallintamalla luonnollisten lukujen joukko sekä sen laskutoimitukset tälle kielelle. Ensimmäinen epätäydellisyyslause sanoo, että RA-kielessä on olemassa validi kaava, joka ei ole teoreema. Toisen epätäydellisyyslauseen mukaan joukko N sekä sitä imitoiva RA-kieli on tarpeeksi kehittynyt matemaattinen järjestelmä, ettei sen ristiriidattomuutta pystytä todistamaan syntaktisesti. Tällaisen järjestelmän ristiriidattomuutta ei voida siis osoittaa päättelyjonoa konstruoimalla. Tutkielman luvussa 1 esitellään ensin primitiivirekursion avulla primitiivirekursiiviset funktiot ja joukot. Yleisesti voidaan sanoa, että primitiivirekursiivisilla funktioilla ja joukoilla tarkoitetaan sellaisia matemaattisia objekteja, joiden laskettavuus pysyy äärellisillä toimenpiteillä hallussa. Käytännössä tämä näkyy esimerkiksi rajoitetun minimalisaation määritelmässä, jossa minimiä etsitään jostain äärellisestä joukosta. Tämän jälkeen kappaleessa 1.2 konstruoidaan RA-kielen syntaksi sekä semantiikka lähes vastaavalla tavalla kuin predikaattikielissä. Luvussa 2 esitellään Gödelin töiden keskeisimmät saavutukset. Ensin esitetään alkulukuesityksen yksikäsitteisyyteen perustuva Gödel-numerointi, jolla jokainen RA-kielen kaava sekä kaavajono saadaan vastaamaan yksikäsitteistä luonnollista lukua. Tämän avulla osoitetaan suurpiirteisesti, kuinka päättelyn primitiivirekursiivisuus voidaan todistaa. Päättelyn primitiivirekursiivisuus on tärkein, mutta myös vaikein aputulos, jota tarvitaan epätäydellisyyslauseiden todistamisessa. Luvun 2 lopuksi epätäydellisyyslauseiden todistukset pyritään esittämään mahdollisimman eksaktisti, kuitenkin samalla selittäen kansantajuisesti etenkin niiden merkityksestä, sekä mitä epätäydellisyyslauseet kertovat matemaattisista järjestelmistä. Viimeisessä luvussa 3 esitellään Gödelin tulosten seurauksia sekä piirretään mahdollisia uusia suuntaviivoja matemaattisen logiikan tutkimuksessa.