### 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