A dichotomy in classifying quantifiers for finite models

by Doron and Shelah. [DoSh:801]
J Symbolic Logic, 2005
We consider a family {U} of finite universes. The second order quantifier Q_{{R}}, means for each U in {{U}} quantifying over a set of n({{R}})-place relations isomorphic to a given relation. We define a natural partial order on such quantifiers called interpretability. We show that for every Q_{{R}}, ever Q_{{R}} is interpretable by quantifying over subsets of U and one to one functions on U both of bounded order, or the logic L(Q_{{R}}) (first order logic plus the quantifier Q_{{R}}) is undecidable.

Back to the list of publications