Preservation and definability for the fluted fragment

Abstract

This paper investigates preservation and definability for the equality-free fluted fragment over finite relational signatures. We first prove an equirank homomorphism preservation theorem: every homomorphism-preserved fluted sentence has an existential-positive fluted equivalent of no greater quantifier rank. We then refute Purdy's claimed Los--Tarski preservation theorem for the fluted fragment. Our counterexample is a rank-three sentence over one binary relation that is preserved under extensions but has no existential fluted equivalent. Finally, a two-variable counterexample over a unary base signature shows that weak and ordinary Beth definability both fail. All three results hold over all structures and over finite structures.

arXiv comment25 pages, 1 table. Substantially expanded version of v1: adds an equirank homomorphism preservation theorem and Beth-definability counterexamples, and adopts the LMCS style