Preservation and definability for the fluted fragment
arXiv:2607.12970
The paper disproves a claimed extension of the Los‑Tarski preservation theorem to the fluted fragment by presenting a quantifier‑rank‑3 fluted sentence that is preserved under extensions but not equivalent to any existential fluted sentence, even on finite structures.
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.
25 pages, 1 table. Substantially expanded version of v1: adds an equirank homomorphism preservation theorem and Beth-definability counterexamples, and adopts the LMCS style