Kirjoitin Gödelin ensimmäisestä epätäydellisyyslauseesta aiemmin. Koska teen oppimateriaalia aiheesta, perehdyn useampaan erilaiseen todistustekniikkaan asian tiimoilta. Mainitsin Gödel-numeroinnin aiemmin. Numerointeja voidaan tehdä monta, mutta ehkä helpoimmin hahmotettavan luin kirjasta A Course in Mathematical Logic. Siinä symbolinen esitys koodataan tekijöihinjakoon niin, että voimme koodata mielivaltainen määrä lukuja, y0,...,yn lukuun x niin, että x = p0y0 * ... *pnyn, missä pn on n:s alkuluku (p0 = 2). Tämä esitys on yksikäsitteinen, koska alkutekijöihin jako on yksikäsitteinen. n:s alkuluku voidaan ilmaista lukuteorian käsittein ensimmäisen kertaluvun kaavalla, joten mitään ongelmaa tässä ei ole.
Tätä esitystapaa noudattaen jokaiselle kaavalle voidaan antaa hyvinkin helposti numerointi. Hyvä johdanto epätäydellisyyslauseeseen on ns. Tarskin lause. Me voimme antaa aritmeettisille kaavoille numeroinnin, esimerkiksi niin, että vakiolle nolla annetaan numero 1. Numeroimme kaikki muuttujat juoksevalla numeroinnilla v1, v2... ja annamme muuttujalle vi numeroin 3i. Seuraajafunktio s() toimii niin, että kaavalle s(r) annetaan numero, joka on 2*3#r missä #r on r:n numerointi. Kaavalle r + t annetaan numero joka on 4*3#r*5#t, ja niin edelleen. Olennaista on, että numerointi on yksikäsitteinen kaikille kaavoille. esimerkiksi kaavalle v1 = 1 tulisi numeroinniksi 6750000.
Tarskin lause sanoo, että predikaatti T(x) joka on tosi kun x on numero jollekin todelle aritmeettiselle lauseelle, ei ole esitettävissä aritmetiikan avulla. Todistus perustuu ns diagonalisointiin. Siinä rakennetaan aritmeettisesti diagonaalisekvenssi d(x) joka käyttäytyy siten, että kun A on kaava, jossa on yksi vapaa muuttuja, ja #A on kaavan numero, niin d(#A) = #(A(#A)), eli d(#A) antaa sen kaavan numeron, joka saadaan kun kaavan parametriksi laitetaan kaavan oma numerointi. Esimerkiksi jos A on kaava "v1 = 1", niin d(6750000) arvoksi tulee kaavan "6750000 = 1" numero. (se on valtavan suuri..)
Jos T(x) olisi aritmeettisesti esitettävä (totuusarvoinen) funktio, meillä olisi kaava joka olisi tosi kun x on toden kaavan numero. Tällöin olisi, yhtä lailla, aritmeettisesti esitettävissä funktio !T(d(x)), eli meillä olisi kaava, joka olisi tosi silloin kun d(x) ei ole toden kaavan numero. Olkoon tämä kaava B.
Tällöin B(x) pätee tasan silloin kun T(x) on epätosi. Koska B olisi aritmeettinen kaava, sillä olisi numerointi. B(#B) olisi siis tosi tasan silloin kun T(d(#B)) olisi epätosi. Mutta kun T(d(#B)) on määritelmällisesti tosi silloin kun B(#B) on tosi, mikä johtaa ristiriitaan. Tämä ristiriita johtuu oletuksesta, että T(x) olisi esitettävissä aritmeettisesti; se ei siis voi olla. Aritmeettiset totuudet eivät siis ole aritmeettisia väittämiä!
Gödelin epätäydellisyyslause on tästä tavallaan hieman hienostelevaisempi versio. Siinä todistetaan, että jos meillä on konsistentti aksiomatisointi aritmetiikalle, niin voimme löytää aritmeettisesti toden kaavan, joka ei ole seuraus tästä aksiomatisoinnista; jokainen aksiomatisointi aritmeettisille totuuksille on epätäydellinen. Myös tämä perustuu diagonalisoinnille.
Aiemmin esittämäni versio epätäydellisyyslauseesta, siis siitä että on olemassa aritmeettisia tosiasioita joita ei voi todistaa, on tavallaan tämä esitettynä toisin. Siinä lähdetään oletuksesta, että aksiomat ja ja päättelysäännöt mumeroidaan, ja johdetaan väittämä "tälle lauseelle ei ole todistusta". Kyseinen lause siis ei voi seurata niistä aksiomista jotka on numeroitu. Se on kuitenkin yhteensopiva aksiomien kanssa, mikäli ne ovat konsistentit. Standardi aritmetiikka siis pysyy voimassa, vaikka lisäsisimme ko. lauseen aksiomien joukkoon. Tästä ei seuraa ristiriitaista aksiomajoukkoa, koska uusi aksioma on oikeastaan muotoa "Tälle lauseelle ei ole todistusta joukosta X lähtien", mutta lause itse ei tietystikään kuulu X:ään. Lisäämisen jälkeen jokainen aksioma on teoreema, tietenkin.
Ei kommentteja:
Lähetä kommentti