Ehrenfeuchtin ja Fraïssén peli
NIEMINEN, PIIA (2008)
NIEMINEN, PIIA
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.
Hyväksymispäivämäärä
2008-11-26
Julkaisun pysyvä osoite on
https://urn.fi/urn:nbn:fi:uta-1-19456
https://urn.fi/urn:nbn:fi:uta-1-19456
Tiivistelmä
Ehrenfeuchtin ja Fraïssén peli sai alkunsa ranskalaisen Roland Fraïssén tutkimuksista elementaarisen ekvivalenssin parissa. Myöhemmin puolalais-amerikkalainen Andrzej Ehrenfeucht antoi Fraïssén saavuttamille tuloksille peliteoreettisen muotoilun. Ehrenfeuchtin ja Fraïssén peli on malliteorian menetelmä, joka perustuu struktuurien samanlaisuuden tarkasteluun. Menetelmä on osoittautunut erityisen hyödylliseksi logiikoiden ilmaisuvoiman tutkimuksissa. Tässä tutkielmassa Ehrenfeuchtin ja Fraïssén peliä käsitellään äärellisten mallien teorian kannalta. Osoitetaan, että kyseinen menetelmä riittää karakterisoimaan ensimmäisen kertaluvun logiikan ilmaisuvoiman. Lisäksi käsitellään Ehrenfeuchtin ja Fraïssén pelin hyödyllisyyttä toisen kertaluvun logiikassa. Osoitetaan, että eräs Ehrenfeuchtin ja Fraïssén pelin laajennus riittää karakterisoimaan eksistentiaalisen monadisen toisen kertaluvun logiikan ilmaisuvoiman.