Homomorphism preservation theorems

The homomorphism preservation theorem (h.p.t.), a result in classical model theory, states that a first-order formula is preserved under homomorphisms on all structures (finite and infinite) if and only if it is equivalent to an existential-positive formula. Answering a long-standing question in finite model theory, we prove that the h.p.t. remains valid when restricted to finite structures (unlike many other classical preservation theorems, including the o - Tarski theorem and Lyndon's positivity theorem). Applications of this result extend to constraint satisfaction problems and to database theory via a correspondence between existential-positive formulas and unions of conjunctive queries. A further result of this article strengthens the classical h.p.t.: we show that a first-order formula is preserved under homomorphisms on all structures if and only if it is equivalent to an existential-positive formula of equal quantifier-rank. © 2008 ACM.

Duke Scholars

Author Benjamin Rossman Computer Science