Homomorphism preservation theorems
Homomorphism preservation theorems
复制标题
同态保存定理
DOI：
10.1145/1379759.1379763
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Benjamin Rossman
中科院分区：
文献类型：
--
作者：
Benjamin Rossman
同态保持定理（h.p.t.）是经典模型论中的一个结果，它表明一个一阶公式在所有结构（有限和无限）上在同态下保持，当且仅当它等价于一个存在正公式。在回答有限模型论中一个长期存在的问题时，我们证明了当限制在有限结构上时，同态保持定理仍然有效（不像许多其他经典保持定理，包括Łoś - 塔斯基定理和林登正性定理）。这个结果通过存在正公式和合取查询的并之间的对应，延伸到约束满足问题和数据库理论。本文的另一个结果强化了经典的同态保持定理：我们表明一个一阶公式在所有结构上在同态下保持，当且仅当它等价于一个量词秩相等的存在正公式。
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.