Logics of Imperfect Information without Identity

Abstract

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.