A dichotomy in classifying quantifiers for finite models

DOI10.2178/JSL/1129642126MaRDI QIDQ5486252zbMATH OpenOpenAlexFDO

Authors S. Shelah, Mor Doron

Publication date 6 September 2006

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0405091

zbMATH Keywords

finite model theorydefinabilityexpressibilitysecond-order quantifier

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Second- and higher-order model theory (03C85)

Abstract: 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.

Recommendations

• On quantification with a finite universe
• scientific article; zbMATH DE number 1453076
• Definability of second order generalized quantifiers
• Unary quantifiers on finite models
• Generalized quantifiers and pebble games on finite structures

Cites work

• There are just four second-order quantifiers

Cited in

(9)

• A dichotomy result for Ramsey quantifiers
• Relativization of quantifiers in finite models
• The solution equivalence to general models for the RIM quantifier problem
• On quantification with a finite universe
• scientific article; zbMATH DE number 4039872 (Why is no real title available?)
• scientific article; zbMATH DE number 536900 (Why is no real title available?)
• scientific article; zbMATH DE number 218552 (Why is no real title available?)
• A Bicategorical Model for Finite Nondeterminism
• On representing concepts in finite models

This page was built for publication: A dichotomy in classifying quantifiers for finite models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5486252)