tiistai 5. marraskuuta 2013

Kompaktisuus

Kompaktisuus on oikeastaan topologinen käsite, joka viittaa suljettuun ja rajoitettuun joukkoon. Miten ihmeessä siis ns kompaktisuuslause logiikassa sanoo, että (äärettömällä) joukolla logiikan kaavoja on malli jos ja vain jos jokaisella sen äärellisellä osajoukolla on malli? Miten tämä liittyy kompaktisuuteen?

Kompaktisuuslause voidaan todistaa monellakin tapaa. Yksi tapa on hyödyntää Gödelin täydellisyyslausetta. Se nimittäin sanoo, että jos joukosta lauseita ei voida johtaa ristiriitaa, sillä on malli. (Itseasiassa se sanoo tämän kontrapositiivisen: Jos joukko lauseita on tautologia, sillä on todistus, mutta todistus menee silti läpi) . Näin todistettuna näyttääkin helposti siltä, että topologinen kompaktisuus on jotain ihan muuta.

Lauseen voi todistaa kuitenkin toisinkin. Johdatus tähän todistukseen on kovin pitkä, mutta koetan tiivistää. Voimme nimittäin ottaa (äärettömän) kokoelman (potentiaalisia) malleja joukolle kaavoja. Tämä kokoelma voi olla ihan hyvin vaikka mitä kardinaalisuutta, mutta on ehkä helpointa ajatella että mallit voidaan indeksoida jostain numeroituvasta joukosta I peräisin olevilla indekseillä.

 Laadimme "meta-domainin" D, jonka alkiot saadaan niin, että otetaan yksi alkio kunkin indeksoidun mallin domainista.

Määrittelemme "metamallin", joka on joukon I osajoukko. Annetun kaavan X "metamalli" on se I:n indeksien joukko, joilla indeksoiduissa malleissa kaava X pätee. Merkitsemme tätä [X]:llä. Metamallit muodostavat boolen algebran, jolla on erilaisia miellyttäviä ominaisuuksia. Esimerkiksi jos meillä on kaavat X ja Y, niin logiikan kaavan "X ja Y" metamalli on [X]:n ja [Y]:n leikkaus. Tämän metamallin konstruktio on siinä määrin monimutkainen, että jätän sen väliin tässä kohtaa.

Koska metamallien joukko muodostaa boolen algebran, voimme puhua esimerkiksi filttereistä. Kun filtteri F on annettu, se on kokoelma I:n osajoukkoja. Filtteri indusoi ekvivalenssiluokkia; olkoon t ja r termejä. Tällöin t = r pätee joissain malleissa ja joissain ei. [t = r] on siis niiden mallien indeksien joukko, joissa t ja r viittaavat samaan mallin alkioon. Meta-domainin alkiot a ja b sovitaan ekvivalenteiksi, jos [a = b] on filtterissä, eli niiden indeksen joukko joissa a ja b viittaavat samaan alkioon ovat filtterissä.

Muodostamme "supermallin" (sic) niin, että sen domain on metadomainin ekvivalenssiluokkien joukko. Saamme ns. Lósin lauseen: Supermalli on kaavan X malli kun X:n metamalli kuuluu filtteriin.

Kompaktisuus todetaan niin, että jos jokaisella kaavajoukon U äärellisellä osajoukolla on malli, niin otetaan indeksijoukoksi I kaikki U:n äärelliset osajoukot. (Näitä on numeroituva määrä). Jokaiselle indeksille i siis löytyy malli M_i. Määritellään tämän kattojoukko N_i niin, että se on kaikkien niiden indeksien joukko joiden osajoukko M_i on. (ja näitähän löytyy tietenkin äärettömästi).

Otetaan nyt jokin I:n osajoukko, vaikkapa M1,...,Mn. Tällöin näiden kattojoukoille pätee, että M-joukkojen unioni kuuluu N-joukkojen leikkaukseen. Tästä seuraa, että N-joukkojen äärellinen leikkaus on N-joukko! Jokainen Boolen algebran kokoelma sisältyy johonkin ultrafiltteriin. Niinpä N-joukkojen kokoelma sisältyy johonkin I:n ultrafiltteriin F.

Tällöin voimme muodostaa Lósin lauseessa mainitun supermallin F:stä ja I:stä. Tämä supermalli on U:n malli.

Jos nyt antaisimme indeksijoukon olla mielivaltainen, voisimme ottaa I:ksi hyvin suuren mallien joukon. Tällöin, annetulle kaavalle X, Mod(X) on niiden mallien joukko jotka ovat X:n malleja. Nämä joukot muodostavat kannan I:n topologialle. Annetulle kaavajoukolle U,  Mod(U) on *suljettu* joukko, joten kompaktisuuslause toteaa että Mod(X):ien indusoima topologia on kompakti.

6 kommenttia:

Sam Hardwick kirjoitti...

Kiitos kirjoituksesta! Tässäpä jotain mitä en tiennyt / en ollut tullut ajatelleeksi vaikka olen opiskellut jonkin verran sekä topologiaa että matemaattista logiikkaa.

Tiedemies kirjoitti...

Joo, tämä on reunahuomautuksena tuossa kirjassa jota olen luentomateriaalina käyttänyt. Minullekin tämä oli hiukan yllättävä kytkös.

Muutoin tuo boolen algebrojen kautta topologiaan kytkös on mielenkiintoinen. Tosin minulla on ollut viimeaikoina huolestuttava määrä finitistisiä ajatuksia...

Tomi kirjoitti...

Viilataan pilkkua. Väite, että kompakti on suljettu ja rajoitettu joukko on virheellinen. R^n joukko on kyllä kompakti jos ja vain jos se on suljettu ja rajoitettu, metrisessä avaruudessa kompaktit joukot ovat suljettuja ja rajoitettuja, mutta kaikki suljetut ja rajoitetut eivät ole kompakteja. Tämän nähdäkseen ota R^n diskreetillä metriikalla.

Yleisessä topologisessa avaruudessa ei ole metriikkaa, joten rajoittuneisuudesta ei voida puhua.

Tomi kirjoitti...
Kirjoittaja on poistanut tämän kommentin.
Tomi kirjoitti...

TM ei kai nämä finitistit tosissaan väitä, että ääretöntä ei ole olemassa?

Mitä finitistit sanovat joukoista, jotka ovat yhtä mahtavia aidon osajoukkonsa kanssa?

Tiedemies kirjoitti...

Finitismi ei ole ihan niin yksiselitteisen hölmöä kuin miltä näyttäisi.