- A characterization of definability of second-order generalized quantifiers with applications to non-definability
- Journal of Computer and System Sciences
- Volume | Issue number
- 80 | 6
- Pages (from-to)
- Document type
- Interfacultary Research Institutes
Faculty of Humanities (FGw)
- Institute for Logic, Language and Computation (ILLC)
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 Q1⋆ is definable in FO(Q2⋆,<,+,×) for certain first-order quantifiers Q1⋆ and Q2⋆. We use our characterization to show new definability and non-definability results for second-order generalized quantifiers. We also show that the monadic second-order majority quantifier Most1 is not definable in second-order logic.
- go to publisher's site
- In special issue: 18th Workshop on Logic, Language, Information and Computation (WoLLIC 2011)
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.