On second-order generalized quantifiers and finite structures

We consider the expressive power of second-order generalized quantifiers on finite structures, especially with respect to the types of the quantifiers. We show that on finite structures with at most binary relations, there are very powerful second-order generalized quantifiers, even of the simplest possible type. More precisely, if a logic L is countable and satisfies some weak closure conditions, then there is a generalized second-order quantifier 2 which is monadic, unary and simple (i.e. of the same type as monadic second-order There Exists), and a uniformly obtained sublogic of FO(2) which is equivalent to L. We show some other results of the above kind, relating other classes of quantifiers to other classes of structures. For example, if the quantifiers are of the simplest non-monadic type, then the result extends to finite structures of any arity. We further show that there are second-order generalized quantifiers which do not increase expressive power of first-order logic but do increase the power significantly when added to stronger logics. (C) 2002 Elsevier Science B.V. All rights reserved.