THE HIERARCHY THEOREM FOR GENERALIZED QUANTIFIERS

The concept of a generalized quantifier of a given similarity type was defined in [12]. Our main result says that on finite structures diffe rent similarity types give rise to different classes of generalized qu antifiers. More exactly, for every similarity type t there is a genera lized quantifier of type t which is nut 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 Lindstrom [17] wi th a counting argument, We extend his method to arbitrary similarity t ypes.