Lecture Notes in Computer Science, 2011, Volume 6642/2011, 187-200, DOI: 10.1007/978-3-642-20920-8_20

Characterizing Definability of Second-Order Generalized Quantifiers

Juha Kontinen and Jakub Szymanik

View Related Documents

Abstract

We study definability of second-order generalized quantifiers. We show that the question whether a second-order generalized quantifier Q1{\mathcal{Q}}_1 is definable in terms of another quantifier Q2{\mathcal{Q}}_2, the base logic being monadic second-order logic, reduces to the question if a quantifier Q*1{\mathcal{Q}}^{\star}_1 is definable in FO(Q*2, < ,+,×){\rm FO}({\mathcal{Q}}^{\star}_2,<,+,\times) for certain first-order quantifiers Q*1{\mathcal{Q}}^{\star}_1 and Q*2{\mathcal{Q}}^{\star}_2. We use our characterization to show new definability and non-definability results for second-order generalized quantifiers. In particular, we show that the monadic second-order majority quantifier Most1 is not definable in second-order logic.
The first author was supported by grant 127661 of the Academy of Finland. The second author was supported by NWO Vici grant 277-80-001.

Fulltext Preview

Image of the first page of the fulltext document