The hierarchy theorem for generalized quantifiers

Abstract

Abstract The concept of a generalized quantifier of a given similarity type was defined in [12]. Our main result says that on finite structures different similarity types give rise to different classes of generalized quantifiers. More exactly, for every similarity type t there is a generalized quantifier of type t which is not definable in the extension of first order logic by all generalized quantifiers of type smaller than t . This was proved for unary similarity types by Per Lindström [17] with a counting argument. We extend his method to arbitrary similarity types.