Rank hierarchies for generalized quantifiers
Mathematics & Actuarial Science Department
Find in your Library
Journal of Logic and Computation
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. © The Author, 2010. Published by Oxford University Press. All rights reserved.
(2011). Rank hierarchies for generalized quantifiers. Journal of Logic and Computation, 21(2), 287–306.
Keisler, H. Jerome, et al.
"Rank hierarchies for generalized quantifiers." Journal of Logic and Computation, vol. 21,no. 2, 2011, pp. 287–306.