Lokaalisuus ja määriteltävyys
Lehtipuu, Heini (2017)
Lehtipuu, Heini
2017
Matematiikan ja tilastotieteen tutkinto-ohjelma - Degree Programme in Mathematics and Statistics
Luonnontieteiden tiedekunta - Faculty of Natural Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2017-06-15
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:uta-201706262120
https://urn.fi/URN:NBN:fi:uta-201706262120
Tiivistelmä
Tässä tutkielmassa esitellään lokaalisuuden käsite ja sen soveltaminen tietokantakyselyiden määriteltävyyteen. Intuitiivisesti, kysely on lokaali, jos sen tulos riippuu koko tarkasteltavan mallin tai tarkasteltavien mallien sijaan ainoastaan tietyistä jonojen ympäristöistä ja niiden isomorfisuudesta. Predikaattilogiikassa Ehrenfeucht-Fraïssé pelit ovat olleet äärellisten mallien teoriassa käytetyimpiä menetelmiä osoittaa ominaisuuksien määrittelemättömyystuloksia, mutta Ehrenfeucht-Fraïssé pelejä soveltamalla voidaan tutkia kerrallaan vain yksittäisen ominaisuuden määriteltävyyttä. Lokaalisuuden avulla voidaan yleistää predikaattilogiikan ilmaisuvoiman rajoja, kun rekursiivisten mekanismien puuttumisen takia predikaattilogiikassa voidaan ilmaista vain lokaaleja kyselyitä ja näin ollen predikaattilogiikka on lokaali. Predikattilogiikan lokaalisuuden todistaminen perustuu Ehrenfeucht-Fraïssé peleille. Rekursiivisten mekanismien lisäksi predikaattilogiikasta puuttuu tunnetusti myös laskentaominaisuus. Tutkielmassa muodostetaan laskurikvanttorin sekä äärettömien konnektiivien avulla ääretön laskurilogiikka; predikaattilogiikan laajennos, jonka ilmaisuvoima on predikaattilogiikkaa tehokkaampi juuri laskennan osalta. Ehrenfeucht-Fraïssé peleistä johdettavien bijektiivisten pelien avulla saadaan kuitenkin todistettua myös äärettömän laskurilogiikan lokaalisuus. Näin ollen myös äärettömän laskurilogiikan kaavoilla voidaan ilmaista vain lokaaleja kyselyitä eikä äärettömän laskurilogiikan ilmaisuvoima ole predikaattilogiikan ilmaisuvoimaa tehokkaampi rekursiivisia mekanismeja vaativien kyselyiden osalta.