Sh:801

• Doron, M., & Shelah, S. (2005). A dichotomy in classifying quantifiers for finite models. J. Symbolic Logic, 70(4), 1297–1324. arXiv: math/0405091 DOI: 10.2178/jsl/1129642126 MR: 2194248
• 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)

@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}
}