A dichotomy in classifying quantifiers for finite models

2004/05/06 by Mor Doron, Saharon Shelah, Doron, Mor +1
Computer Science · Mathematics · #Advanced Algebra and Logic #FOS: Mathematics #Formal Methods in Verification #Logic (math.LO) #Logic, Reasoning, and Knowledge #math.LO

paper · pdf · doi:10.48550/arxiv.math/0405091

published as J. Symbolic Logic 70 No. 4 (2005) 1297--1324

arxiv created 2004/05/06 · openalex publication_date 2004/05/06 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• On quantification with a finite universe
• Implicitly definable generalized quantifiers
• From Quantifier Depth to Quantifier Number: Separating Structures with k Variables
• Embedded Finite Models Beyond Restricted Quantifier Collapse
• On the Number of Quantifiers as a Complexity Measure