A dichotomy in classifying quantifiers for finite models
Shelah, Saharon ; Doron, Mor
J. Symbolic Logic, Tome 70 (2005) no. 1, p. 1297-1324 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
We consider a family 𝔲 of finite universes. The second order existential quantifier Qℜ, means for each U∈ 𝔲 quantifying over a set of n(ℜ)-place relations isomorphic to a given relation. We define a natural partial order on such quantifiers called interpretability. We show that for every Qℜ, either Qℜ is interpretable by quantifying over subsets of U and one to one functions on U both of bounded order, or the logic L(Qℜ) (first order logic plus the quantifier Qℜ) is undecidable.
Publié le : 2005-12-14
Classification:  
@article{1129642126,
     author = {Shelah, Saharon and Doron, Mor},
     title = {A dichotomy in classifying quantifiers for finite models},
     journal = {J. Symbolic Logic},
     volume = {70},
     number = {1},
     year = {2005},
     pages = { 1297-1324},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1129642126}
}

Shelah, Saharon; Doron, Mor. A dichotomy in classifying quantifiers for finite models. J. Symbolic Logic, Tome 70 (2005) no. 1, pp.  1297-1324. http://gdmltest.u-ga.fr/item/1129642126/