# Sh:801

• Doron, M., & Shelah, S. (2005). A dichotomy in classifying quantifiers for finite models. J. Symbolic Logic, 70(4), 1297–1324.
• Abstract:
We consider a family \mathfrak{U} of finite universes. The second order quantifier Q_{\mathfrak{R}}, means for each U\in {\mathfrak{U}} quantifying over a set of n({\mathfrak{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_{\mathfrak {R}}, ever Q_{\mathfrak {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_{\mathfrak{R}}) (first order logic plus the quantifier Q_{\mathfrak{R}}) is undecidable.
• published version (29p)
Bib entry
@article{Sh:801,
author = {Doron, Mor and Shelah, Saharon},
title = {{A dichotomy in classifying quantifiers for finite models}},
journal = {J. Symbolic Logic},
fjournal = {The Journal of Symbolic Logic},
volume = {70},
number = {4},
year = {2005},
pages = {1297--1324},
issn = {0022-4812},
mrnumber = {2194248},
mrclass = {03C85 (03C13)},
doi = {10.2178/jsl/1129642126},
note = {\href{https://arxiv.org/abs/math/0405091}{arXiv: math/0405091}},
arxiv_number = {math/0405091}
}