A dichotomy in classifying quantifiers for finite models

DOI10.2178/JSL/1129642126zbMATH Open1108.03040arXivmath/0405091OpenAlexW2161787358MaRDI QIDQ5486252FDOQ5486252

Authors: S. Shelah, Mor Doron 

Publication date: 6 September 2006

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

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.

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

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

zbMATH Keywords

finite model theorydefinabilityexpressibilitysecond-order quantifier

Mathematics Subject Classification ID

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

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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)