We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Rank Hierarchies for Generalized Quantifiers.
- Authors
KEISLER, H. JEROME; LOTFALLAH, WAFIK BOULOS
- Abstract
We show that for each n and m, there is an existential first order sentence that is NOT logically equivalent to a sentence of quantifier rank at most m in infinitary logic augmented with all generalized quantifiers of arity at most n. We use this to show the strictness of the quantifier rank hierarchies for various logics ranging from existential (or universal) fragments of first-order logic to infinitary logics augmented with arbitrary classes of generalized quantifiers of bounded arity.The sentence above is also shown to be equivalent to a first-order sentence with at most n+2 variables (free and bound). This gives the strictness of the quantifier rank hierarchies for various logics with only n+2 variables. The proofs use the bijective Ehrenfeucht–Fraïsse game and a modification of the building blocks of Hella.
- Subjects
QUANTIFIERS (Linguistics); FIRST-order logic; MODERN logic; SENTENCES (Grammar); FINITE element method
- Publication
Journal of Logic & Computation, 2011, Vol 21, Issue 2, p287
- ISSN
0955-792X
- Publication type
Article
- DOI
10.1093/logcom/exq019