Logics of Imperfect Information without Identity
Kuusisto, Antti (2011)
2011
Informaatiotieteiden yksikkö - School of Information Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Julkaisun pysyvä osoite on
https://urn.fi/urn:isbn:978-951-44-8229-8
https://urn.fi/urn:isbn:978-951-44-8229-8
Kuvaus
Tämä tekninen raportti on julkaistu epävirallisesti Kööpenhaminassa 2010 pidetyn epämuodollisen workshopin yhteydessä.
Tiivistelmä
We investigate the expressive power of sentences of the family of independence friendly (IF) logics in the equality-free setting. Various natural equality-free fragments of logics in this family translate into the version of existential second-order logic with prenex quantification of function symbols only and with the first-order parts of formulae equality-free.
We study this version of existential second-order logic. Our principal result is that over finite models with a vocabulary consisting of unary relation symbols only, this fragment of second-order logic is weaker in expressive power than first-order logic. Such results could turn out useful in the study of independence-friendly modal logics.
In addition to proving results of a technical nature, we consider issues related to a perspective where IF logic is regarded as a specification framework for games, and also discuss the significance of understanding fragments of second-order logic in investigations related to non-classical logics.
We study this version of existential second-order logic. Our principal result is that over finite models with a vocabulary consisting of unary relation symbols only, this fragment of second-order logic is weaker in expressive power than first-order logic. Such results could turn out useful in the study of independence-friendly modal logics.
In addition to proving results of a technical nature, we consider issues related to a perspective where IF logic is regarded as a specification framework for games, and also discuss the significance of understanding fragments of second-order logic in investigations related to non-classical logics.