Characterizing definability of second-order generalized quantifiers

Authors
Publication date 2011
Host editors
  • L.D. Beklemishev
  • R. de Queiroz
Book title Logic, Language, Information and Computation
Book subtitle 18th International Workshop, WoLLIC 2011, Philadelphia, PA, USA, May 18-20, 2011 : proceedings
ISBN
  • 9783642209192
ISBN (electronic)
  • 9783642209208
Series Lecture Notes in Computer Science
Event Logic, Language, Information and Computation: 18th International Workshop
Pages (from-to) 187-200
Publisher Heidelberg: Springer
Organisations
  • Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
Abstract
We study definability of second-order generalized quantifiers. We show that the question whether a second-order generalized quantifier Q1 is definable in terms of another quantifier Q2, the base logic being monadic second-order logic, reduces to the question if a quantifier Q⋆1 is definable in FO(Q⋆2 ,<,+,×)  for certain first-order quantifiers Q⋆1 and Q⋆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.
Document type Conference contribution
Language English
Published at https://doi.org/10.1007/978-3-642-20920-8_20
Permalink to this page
Back