The Expressive Power of CSP-Quantifiers

A generalized quantifier QK is called a CSP-quantifier if its defining class K consists of all structures that can be homomorphically mapped to a fixed finite template structure. For all positive integers n ≥ 2 and k, we define a pebble game that characterizes equivalence of structures with respect to the logic L^k_∞ω(CSP⁺_n ), where CSP⁺_n is the union of the class Q1 of all unary quantifiers and the class CSPn of all CSP-quantifiers with template structures that have at most n elements. Using these games we prove that for every n ≥ 2 there exists a CSP-quantifier with template of size n + 1 which is not definable in L^ω_∞ω(CSP⁺_n ). The proof of this result is based on a new variation of the well-known Cai-Fürer-Immerman construction.