Syksyn opetuksessa on taas kerran vuorossa matemaattinen logiikka. Tällä viikolla käsittelemme logiikkaa algebran näkökulmasta. Logiikka voidaan ajatella monella eri tavalla. Yksi tavanomaisimpia lähtökohtia on sellainen, jossa logiikka nähdään formaalina kielenä, siis joukkona merkkijonoja, jolla on syntaksi ja semantiikka. Semantiikka puolestaan yleensä määritellään malliteoreettisesti: propositiologiikassa logiikan kaavan semantiikka on niiden propositioarvojen yhdistelmien joukko, jotka tekevät kaavan todeksi. Kaava "p tai q" on siis tosi jos joko p tai q (tai molemmat) saa arvon tosi, ja epätosi jos kumpikaan ei saa.
Ensimmäisen kertaluvun mallit ovat monimutkaisempia. Ensimmäisen kertaluvun kaavat viittaavat muuttujiin joiden arvo pitää jotenkin kiinnittää. Logiikassa sanotaan tällöin asioita kuten "kaikilla x P(x)" tai "jokaista x:ää kohden on olemassa y siten että S(x,y)". Nämä kaavat ovat tosia tai epätosia suhteessa siihen, miten nämä predikaatit määritellään jossakin joukossa. Esimerkiksi jos P(x) on tosi joillekin mallijoukon alkioille ja epätosi joillekin, malli ei toteuta väittämää "kaikilla x P(x)". (Pahoittelen että käytän proosaa, logiikan symbolit ovat kovin työläitä lisätä bloggerissa).
Toinen tapa nähdä logiikka on ajatella kaavaa tapana esittää jokin looginen funktio, jonka totuusarvo riippuu sen symboleille annetuista merkityksistä. Tällöin loogiset konnektiivit kuten "ja", "tai" tai negaatio, voidaan nähdä algebrallisina operaatioina näiden funktioiden joukolle. Kun logiikan symbolit on fiksattu, mahdollisten kaavojen joukko on kiinteä. Näille kaavoille voidaan esittää ekvivalenssirelaatio, joka nimensä mukaisesti samastaa loogisesti yhtäpitävät kaavat. Nämä ekvivalenssiluokat muodostavat Boolen algebran. Kuten muistamme, Boolen algebra on distributiivinen ja komplementilla varustettu hila. Boolen algebrat tarjoavat erittäin käytännöllisen tavan puhua logiikan avulla esitettävistä teorioista. Niiden ilmaisuvoima riippuu siitä, onko käytössä valinta-aksiooma vai ei, ks.
Kun olen käsitellyt algebrallisen lähestymistavan, siirryn täydellä voimalla malliteoriaan. Ensimmäisen kertaluvun malliteoriasta puhuminen on hieman Münchausenilaista itsensä niskasta nostamista, koska malleista ei voi oikein puhua ilman että käytetään korkeamman kertaluokan ilmaisuja. Malliteorian helmenä esitämme lopulta Löwenheim-Skolemin teoreeman.
Todistus ei ole mitenkään erityisen vaikea, mutta sen ymmärrettyäni minulle tuli sellainen tunne, että olen tullut huijatuksi; samainen tunne tuli, kun lopulta ymmärsin miten Gödelin ensimmäinen epätäydellisyyslause toimii. Kyseessä on jotain mikä muistuttaa korttitemppua, jossa taikuri näyttää jonkin näennäisesti mahdottoman tempun, ja lopulta paljastuu että hänellä onkin useampi samanlainen pakka selän takana.
Todistus (alaspäin) L-S-teoreemalle perustuu seuraavanlaiseen temppuun: Meillä on jokin aksiomatisointi ja malli teorialle. Mallin kardinaalisuus saa olla mitä hyvänsä, sillä ei ole väliä. Nappaamme mallista jonkin alkion, tai jos niin haluamme, numeroituvan määrän alkioita, olkoon tämä joukko X. Määrittelemme numeroituvan jonon joukkoja, B(i) ja numeroituvan perheen funktioita Y(i,P). B(0) = X, ja Y(i,P) on funktio joka tuottaa kaavasta P joukon mallin alkoita x siten,
että P(a1,...,an,x) voidaan tehdä todeksi valitsemalla alkiot a1...an joukosta B(i). B(i+1) puolestaan sisältää yhden alkion jokaisesta joukosta Y(i,P), siten että P käy yli teorian aksiomissa esiintyvien osakaavojen (voimme olettaa aksiomilta tietynlaisen kanonisen muodon). Jono B(i) konvergoituu kohti teorian mallia (tämän osoittamiseksi täytyy käyttää muutamaa apulausetta, ja esitys tässä on hieman epätarkka muutenkin), ja koska konstruktio on numeroituva, tämä tuottaa numeroituvan mallin teorialle.
Tässä käytetään hyvin rankalla kädellä valinta-aksioomaa. Valinta-aksiooma sanoo, että mielivaltaiselle joukkoperheelle on olemassa ns. valintafunktio, eli funktio joka poimii yhden alkion jokaisesta perheen alkiosta, ja sen kuvajoukko on hyvinmääritelty joukko. Tämä on intuitiivisesti ilmeinen äärellisillä ja miksei numeroituvillakin konstruktioilla, mutta johtaa kaikenlaiseen erikoiseen. Siitä olenkin jo satuillut joten ei sen enempää.
Löwenheim-Skolem on minusta mielenkiintoinen lähinnä siksi että se paljastaa että ensimmäisen kertaluvun logiikalla ei voi ilmaista erisuuruisia äärettömyyksiä. Esimerkiksi reaalilukujen ensimmäisen kertaluvun karakterisoinnit eivät pakota ylinumeroituvaa mallia, eikä ylinumeroituvuutta siten voi todistaa missään ensimmäisen kertaluvun teoriassa. Tähän kohtaan on kuitenkin syytä huomioida, että käytännössä kaikki reaalilukujen täydellisyyden aksiomatisoinnit ovat itseasiassa (monadisia) toisen asteen väittämiä.
Ei kommentteja:
Lähetä kommentti