0-1 lait äärellisissä malleissa

Abstract

Äärellisten mallien teoria on tietotekniikan kehityksen tarpeiden seurauksena kasvanut matemaattisen logiikan osa-alue. Teorian ensimmäisiä tuloksia oli Trakhtenbrotin tulos vuodelta 1950, jonka mukaan validius äärellisissä malleissa ei ole rekursiivisesti numeroituva. Nykyisin äärellisten mallien logiikat ovat usein perusta tietokantakyselyiden luomiseen ja äärellisten mallien teorian tekniikoiden avulla todistetaan hakujärjestelmien ilmaisuvoimaa ja monimuotoisuutta.

Äärellisissä malleissa, kuten suuntaamattomissa äärellisissä verkoissa, voidaan tutkia tietyn ominaisuuden toteutuvuuden todennäköisyyttä. Kun verkon solmujen määrä lähenee ääretöntä, saadaan ominaisuudelle asymptoottinen todennäköisyys. Matemaattisessa logiikassa hyvin mielenkiintoinen ilmiö on 0–1 lait, jotka käsittelevät ominaisuuksien asymptoottista todennäköisyyttä eri logiikoissa. Jos logiikalla on 0–1 laki, kaikkien siinä määriteltävien ominaisuuksien asymptoottinen todennäköisyys on 0 tai 1. Tässä tutkielmassa esitellään muutamia logiikoita ja tutkitaan onko niillä 0–1 laki.

Työssä tutustutaan aluksi verkkojen ominaisuuksiin ja määritellään kiintopisteen käsite, sekä muutama kiintopistelogiikka. Kiintopistelogiikoiden käsittelyä jatketaan määrittelemällä rajoitetun muuttujamäärän logiikat. Ehrenfeucht-Fraïssén peleistä esitellään helmipelit, joiden avulla saadaan todistettua tärkeitä tuloksia liittyen asymptoottisiin todennäköisyyksiin ja kyselyihin eri logiikoissa. Työn lopussa määritellään vielä laajennusaksioomat, jotka ovat tarpeellinen apuväline 0–1 lain todistamisessa.

Viitekirjoina työssä ovat Libkin, Leonid: Elements of Finite Model Theory ja Ebbinghaus, Heinz-Dieter & Flum, Jorg: Finite Model Theory.