Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T15:46:35.137Z Has data issue: false hasContentIssue false

A dichotomy in classifying quantifiers for finite models

Published online by Cambridge University Press:  12 March 2014

Saharon Shelah
Affiliation:
The Hebrew University of Jerusalem, Einstein Institute of Mathematics, Edmond Safra Campus, Givat Ram, Jerusalem 91904, IsraelDepartment of Mathematics, Hill Center-Busch Campus Rutgers, The State University of New Jersey, 110 Frelinghuysen Road, Piscataway, NJ 08854-8019, USA, E-mail: shelah@math.huji.ac.il
Mor Doron
Affiliation:
The Hebrew University of Jerusalem, Einstein Institute of Mathematics, Edmond Safra Campus, Givat Ram, Jerusalem 91904, IsraelDepartment of Mathematics, Hill Center-Busch Campus Rutgers, The State University of New Jersey, 110 Frelinghuysen Road, Piscataway, NJ 08854-8019, USA, E-mail: shelah@math.huji.ac.il

Abstract

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.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2005

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable