A characterization of definability of second-order generalized quantifiers with applications to non-definability

作者：

Highlights：

• We characterize the definability of second-order generalized quantifiers:

• Q1 is definable in MSO(Q2,+) iff Q1⁎ is definable in FO(Q2⁎,+,×).

• We use our characterization to proof new definability results, e.g.:

• The monadic second-order majority quantifier is non-definable in SO.

• We discuss consequences for the linguistic semantics of collective quantifiers.

摘要

•We characterize the definability of second-order generalized quantifiers:•Q1 is definable in MSO(Q2,+) iff Q1⁎ is definable in FO(Q2⁎,+,×).•We use our characterization to proof new definability results, e.g.:•The monadic second-order majority quantifier is non-definable in SO.•We discuss consequences for the linguistic semantics of collective quantifiers.

论文关键词：Second-order generalized quantifiers,Definability,Majority quantifier,Second-order logic,Collective quantification

论文评审过程：Received 14 January 2012, Revised 21 February 2013, Accepted 3 February 2014, Available online 4 April 2014.

论文官网地址：https://doi.org/10.1016/j.jcss.2014.04.007