Characterizing Definability of Second-Order Generalized Quantifiers

In L. Beklemishev & R. de Queiroz (eds.), Proceedings of the 18th Workshop on Logic, Language, Information and Computation, Lecture Notes in Artificial Intelligence 6642. Springer (2011)
  Copy   BIBTEX

Abstract

We study definability of second-order generalized quantifiers. We show that the question whether a second-order generalized quantifier $\sQ_1$ is definable in terms of another quantifier $\sQ_2$, the base logic being monadic second-order logic, reduces to the question if a quantifier $\sQ^{\star}_1$ is definable in $\FO(\sQ^{\star}_2,<,+,\times)$ for certain first-order quantifiers $\sQ^{\star}_1$ and $\sQ^{\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 $\most^1$ is not definable in second-order logic.

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,757

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

The Hierarchy Theorem for Second Order Generalized Quantifiers.Juha Kontinen - 2006 - Journal of Symbolic Logic 71 (1):188 - 202.
Definability of second order generalized quantifiers.Juha Kontinen - 2010 - Archive for Mathematical Logic 49 (3):379-398.
On second-order generalized quantifiers and finite structures.Anders Andersson - 2002 - Annals of Pure and Applied Logic 115 (1--3):1--32.
Generalized quantifiers and modal logic.Wiebe Hoek & Maarten Rijke - 1993 - Journal of Logic, Language and Information 2 (1):19-58.
Generalized quantifiers and modal logic.Wiebe Van Der Hoek & Maarten De Rijke - 1993 - Journal of Logic, Language and Information 2 (1):19-58.
A remark on collective quantification.Juha Kontinen & Jakub Szymanik - 2008 - Journal of Logic, Language and Information 17 (2):131-140.
Logical Hierarchies in PTIME.Lauri Hella - 1996 - Information And Computation 129 (1):1--19.
Quantifiers.Dag Westerståhl - 2001 - In Lou Goble (ed.), The Blackwell Guide to Philosophical Logic. Malden, Mass.: Wiley-Blackwell. pp. 437–460.

Analytics

Added to PP
2011-05-31

Downloads
76 (#277,792)

6 months
4 (#1,269,568)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Jakub Szymanik
University of Amsterdam

References found in this work

No references found.

Add more references