Generalizing the Goldblatt-Thomason Theorem and Modal Definability
Lehtinen, Suvi (2008)
Lehtinen, Suvi
Tampere University Press
2008
Matematiikka - Mathematics
Informaatiotieteiden tiedekunta - Faculty of Information Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Väitöspäivä
2008-11-07
Julkaisun pysyvä osoite on
https://urn.fi/urn:isbn:978-951-44-7515-3
https://urn.fi/urn:isbn:978-951-44-7515-3
Tiivistelmä
Määriteltävyysteoria tutkii erilaisia kieliä ja niiden ilmaisuvoimaa. Niinpä modaalilogiikan määriteltävyysteoria, johon tämä työ kuuluu, tutkii erilaisten modaalisten kielten ilmaisuvoimaa. Tarkasteltava kieli määrittelee syntaksin eli lauseiden muodon/rakenteen ja käytettävissä olevat mallit semantiikan eli lauseiden tulkinnan.
Tässä työssä tarkasteltavana kielenä on perusmodaalilogiikka ja sen eräät laajennukset. Blackburn, de Rijke ja Venema luonnehtivat eräässä modaalilogiikan perusteoksessaan modaalisia kieliä yksinkertaisiksi kieliksi, joiden avulla voidaan puhua relationaalisista struktuureista. Yksinkertaisuus tulee siitä, että perusmodaalilogiikka saadaan lauselogiikasta lisäämällä siihen modaalinen operaattori, jonka avulla kaavojen totuutta voidaan arvioida myös suhteessa mallin muihin tiloihin/maailmoihin. Siinä missä tavallisessa lauselogiikassa kaava on tosi tai epätosi vain osastensa totuusarvoista riippuen, modaalilogiikassa kaavan totuus mallissa voi riippua yhdestä tai useammasta muusta maailmasta, joiden kanssa tarkasteltava maailma on relaatiossa. Tavallisimmat modaalioperaattorit ovat "mahdollisuus"- ja "välttämättömyysoperaattorit", jotka tulkitaan relationaalisessa mallissa (suunnattu graafi): Asiantila on mahdollinen, jos tarkasteltavasta tilasta pääsee johonkin tilaan, jossa se on tosi, ja asiantila on välttämätön, jos se on tosi kaikissa mahdollisissa maailmoissa, joihin tarkasteltavasta tilasta on mahdollista päästä.
Semantiikan tarjoavat relationaaliset kehykset, jotka koostuvat tiloista ja relaatio(i)sta niiden välillä. Kielessä oleville propositiosymboleille olisi myös mahdollista antaa tulkinnat, jotka kertoisivat missä maailmoissa mitkäkin propositiot ovat tosia, mutta tässä työssä liikutaan pääsääntöisesti kehysten tasolla, jolloin keskeiseksi käsitteeksi nousee totuuden asemesta validisuus. Kaava on validi kehyksessä, mikäli se on tosi kehyksen jokaisessa tilassa propositiosymboleille annetusta tulkinnasta riippumatta. Tämä antaa yhden tavan määritellä määriteltävyyden käsitteen sanotaan, että kehysluokka on määriteltävissä kielessä L, mikäli on olemassa kielen L kaava(joukko), joka on validi täsmälleen määriteltävänä olevan kehysluokan kehyksissä.
Alkuperäisenä lähtökohtana tälle tutkimukselle oli Goldblatt-Thomasonin lause, jonka mukaan ensimmäisen kertaluvun logiikassa määriteltävät kehysluokat ovat määriteltävissä tavallisessa modaalilogiikassa täsmälleen silloin kuin nämä kehysluokat ovat suljettuja tiettyjen kehyskonstruktioiden suhteen. Työssä on esitetty tällä klassiselle tulokselle useita variaatioita. Näitä on saavutettu kahdella tavalla: rajaamalla tarkasteltavia kehysluokkia ja toisaalta laajentamalla käytettävää modaalilogiikan kieltä.
Työn omaperäisin osa koostuu luvusta 5, jossa esitellään luonnollinen laajennus kehysvalidisuudelle. Siinä missä tavallinen kehysvalidisuus vastaa kvantifiointia osajoukkojen yli, siirrytään tässä uudessa validisuuden käsitteessä tarkastelemaan tapausta, jossa on mahdollista kvantifioida myös osa kaavan tulkinnassa käytettävistä relaatioista. Kvantifioitavia relaatioita (ja niitä vastaavia modaalioperaattoreita) kutsutaan apulaisiksi (helpers) ja varsinaisia relaatioita (ja niitä vastaavia modaalioperaattoreita) pomoiksi (bosses). Tämä kasvattaa ilmaisuvoimaa, mutta säilyttää kuitenkin joitakin tutuista kehyskonstruktioista. Viimeisessä kappaleessa esitellään vielä assistetit, joiden tulkinta voi riippua alla olevan kehyksen relaatio(i)sta (boss-dependent) tai vain maailmoista (boss-independent), kuten vaikkapa globaalin modaliteetin tapauksessa. Lopuksi tarkasteluun otetaan mukaan vielä toteutuvuuden invarianssi-ehto, joka avulla voidaan tarkastella myös sellaisia vain maailmoista riippuvia assistentteja kuin lineaarijärjestys tai seuraajarelaatio. Työ viimeinen luku avaa uusia ovia ja jättää runsaasti tutkittavaa myös tuleville tutkijasukupolville.
Tässä työssä tarkasteltavana kielenä on perusmodaalilogiikka ja sen eräät laajennukset. Blackburn, de Rijke ja Venema luonnehtivat eräässä modaalilogiikan perusteoksessaan modaalisia kieliä yksinkertaisiksi kieliksi, joiden avulla voidaan puhua relationaalisista struktuureista. Yksinkertaisuus tulee siitä, että perusmodaalilogiikka saadaan lauselogiikasta lisäämällä siihen modaalinen operaattori, jonka avulla kaavojen totuutta voidaan arvioida myös suhteessa mallin muihin tiloihin/maailmoihin. Siinä missä tavallisessa lauselogiikassa kaava on tosi tai epätosi vain osastensa totuusarvoista riippuen, modaalilogiikassa kaavan totuus mallissa voi riippua yhdestä tai useammasta muusta maailmasta, joiden kanssa tarkasteltava maailma on relaatiossa. Tavallisimmat modaalioperaattorit ovat "mahdollisuus"- ja "välttämättömyysoperaattorit", jotka tulkitaan relationaalisessa mallissa (suunnattu graafi): Asiantila on mahdollinen, jos tarkasteltavasta tilasta pääsee johonkin tilaan, jossa se on tosi, ja asiantila on välttämätön, jos se on tosi kaikissa mahdollisissa maailmoissa, joihin tarkasteltavasta tilasta on mahdollista päästä.
Semantiikan tarjoavat relationaaliset kehykset, jotka koostuvat tiloista ja relaatio(i)sta niiden välillä. Kielessä oleville propositiosymboleille olisi myös mahdollista antaa tulkinnat, jotka kertoisivat missä maailmoissa mitkäkin propositiot ovat tosia, mutta tässä työssä liikutaan pääsääntöisesti kehysten tasolla, jolloin keskeiseksi käsitteeksi nousee totuuden asemesta validisuus. Kaava on validi kehyksessä, mikäli se on tosi kehyksen jokaisessa tilassa propositiosymboleille annetusta tulkinnasta riippumatta. Tämä antaa yhden tavan määritellä määriteltävyyden käsitteen sanotaan, että kehysluokka on määriteltävissä kielessä L, mikäli on olemassa kielen L kaava(joukko), joka on validi täsmälleen määriteltävänä olevan kehysluokan kehyksissä.
Alkuperäisenä lähtökohtana tälle tutkimukselle oli Goldblatt-Thomasonin lause, jonka mukaan ensimmäisen kertaluvun logiikassa määriteltävät kehysluokat ovat määriteltävissä tavallisessa modaalilogiikassa täsmälleen silloin kuin nämä kehysluokat ovat suljettuja tiettyjen kehyskonstruktioiden suhteen. Työssä on esitetty tällä klassiselle tulokselle useita variaatioita. Näitä on saavutettu kahdella tavalla: rajaamalla tarkasteltavia kehysluokkia ja toisaalta laajentamalla käytettävää modaalilogiikan kieltä.
Työn omaperäisin osa koostuu luvusta 5, jossa esitellään luonnollinen laajennus kehysvalidisuudelle. Siinä missä tavallinen kehysvalidisuus vastaa kvantifiointia osajoukkojen yli, siirrytään tässä uudessa validisuuden käsitteessä tarkastelemaan tapausta, jossa on mahdollista kvantifioida myös osa kaavan tulkinnassa käytettävistä relaatioista. Kvantifioitavia relaatioita (ja niitä vastaavia modaalioperaattoreita) kutsutaan apulaisiksi (helpers) ja varsinaisia relaatioita (ja niitä vastaavia modaalioperaattoreita) pomoiksi (bosses). Tämä kasvattaa ilmaisuvoimaa, mutta säilyttää kuitenkin joitakin tutuista kehyskonstruktioista. Viimeisessä kappaleessa esitellään vielä assistetit, joiden tulkinta voi riippua alla olevan kehyksen relaatio(i)sta (boss-dependent) tai vain maailmoista (boss-independent), kuten vaikkapa globaalin modaliteetin tapauksessa. Lopuksi tarkasteluun otetaan mukaan vielä toteutuvuuden invarianssi-ehto, joka avulla voidaan tarkastella myös sellaisia vain maailmoista riippuvia assistentteja kuin lineaarijärjestys tai seuraajarelaatio. Työ viimeinen luku avaa uusia ovia ja jättää runsaasti tutkittavaa myös tuleville tutkijasukupolville.
Kokoelmat
- Väitöskirjat [4776]