Lokaalisuus ja määriteltävyys

Abstract

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.