Fefermanin-Vaughtin lause mallipareille

Abstract

Tässä tutkielmassa esitellään ensimmäisen kertaluvun logiikassa tunnettu Fefermanin–Vaughtin lause, joka tarjoaa menetelmän yhdistetyn mallin ominaisuuksien tutkimiseen sen komponenttimallien ominaisuuksien avulla. Koska tutkielman tavoitteena on tutustuttaa lukija lauseen perusideaan, tarkastelu rajoitetaan vain erillisiin mallipareihin eli sellaisiin mallipareihin, jotka eivät jaa mitään yhteisiä alkioita tai rakenteellisia suhteita.

Tutkielma alkaa johdannolla, jossa perehdytään hieman Fefermanin–Vaughtin lauseen historiaan ja käyttökohteisiin sekä esitellään tutkielman rakenne. Lisäksi käydään läpi tarvittavia ennakkotietoja, kuten tutkielman aikana käytettävät merkintätavat.

Seuraavan luvun alussa käsitellään predikaattilogiikan peruskäsitteitä, kuten kaava, lause ja malli. Näistä annetaan myös kattavat esimerkit, jotta perusteet olisivat mahdollisimman hyvin hallussa ennen eteenpäin siirtymistä. Tämän jälkeen esitellään kvanttoriasteen määritelmä ja todistetaan apulause, joka osoittaa, että äärellisessä relationaalisessa aakkostossa on vain äärellinen määrä tiettyä kvanttoriastetta olevia lauseita. Samassa luvussa käsitellään myös mallien välinen ekvivalenssi sekä malliparien määritelmä.

Luvussa 3 esitellään mallien vertailua isomorfismin avulla, minkä jälkeen perehdytään Ehrenfeuchtin ja Fraïssén peliin. Samalla esitetään lause kahden mallin välisen isomorfismin ja Ehrenfeuchtin–Fraïssén pelin voittostrategian olemassaolon yhtäpitävyydestä sekä vastaava lause mallien väliselle ekvivalenssille. Luvun lopuksi todistetaan lause ekvivalenssin säilyvyydestä malliparissa, tarkastellaan siihen liityvää esimerkkiä sekä esitetään ja todistetaan Fefermanin–Vaughtin lause.