Rank hierarchies for generalized quantifiers

Author's Department

Mathematics & Actuarial Science Department

Find in your Library

https://doi.org/10.1093/logcom/exq019

Document Type

Research Article

Publication Title

Journal of Logic and Computation

Publication Date

4-1-2011

doi

10.1093/logcom/exq019

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. © The Author, 2010. Published by Oxford University Press. All rights reserved.

First Page

287

Last Page

306

This document is currently not available here.

Find this item online

Share

COinS