Quantifying over Quantifiers (Abstract)

AbstractWe study existential and universal quantification over quantifiers, i.e. quantification where the objects quantified over are Lindstrom quantifiers. First we consider the fragment where only existential quantification over quantifiers is allowed, denoted ΣQ1. We show that ΣQ1 includes inflationary fixed-point logic extended with the ability to express that two defined structures are non-isomorphic, and that ΣQ1 is included in existential second-order logic with the same extension.The logic ΣQn is defined as the fragment where we alternate existential and universal quantification for n levels. We show that ΣQn+1 is included in the n-th level of the complexity theoretical exponential hierarchy. We also show that there is a hierarchy on the arity of the quantifier variables, by showing that no fragment of ΣQn with restricted arity of the quantifiers can express all ΣQ1 properties