Quantifiers Closed Under Partial Polymorphisms

Anuj Dawar and Lauri Hella

4:00 - 4:35PM, Sat, Jun 24.
Abstract (PDF)

We consider Lindström quantifiers that are closed under operations we term partial polymorphisms. These generalize the closure conditions on CSP quantifiers CSP(B) (as considered in Hella, CSL 2023) based on the polymorphisms of the template B. We devise a pebble game which can be used to demonstrate inexpressibility in the infinitary logic expanded with all quantifiers closed under a fixed family of partial polymorphisms. We use this and a CFI-like construction to exhibit a property that is not definable in the infinitary logic extended with all quantifiers closed under a near-unanimity polymorphism.

[Back to Schedule]