Abstract

We consider a family U of finite universes. The second order existential quantifier QR. means for each U ϵ U quantifying over a set of n(R)-place relations isomorphic to a given relation. We define a natural partial order on such quantifiers called interpretability. We show that for every QR. either QR is interpretable by quantifying over subsets of U and one to one functions on U both of bounded order, or the logic L(QR) (first order logic plus the quantifier QR) is undecidable