Ehrenfeuchtin ja Fraïssén peli

Abstract

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.