论文标题
树木类别和等级同构保护定理
Arboreal Categories and Equi-resource Homomorphism Preservation Theorems
论文作者
论文摘要
经典的同态保存定理，由于lyoś，Lyndon和Tarski，指出一阶句子$ ϕ $被保留在结构之间的同构中，并且只有当它等效于存在的正面句子$ψ$。鉴于句子的（句法）复杂性的概念，“等级”同构保护定理可以通过确保可以选择$ψ$来改善经典结果，以便其复杂性不超过$ ϕ $。 我们描述了一种基于树木类别概念的均值同态保存定理的公理方法。然后，使用该框架来建立新颖的同态保存结果，并改善已知逻辑片段，包括一阶，守护和模态逻辑。
The classical homomorphism preservation theorem, due to Łoś, Lyndon and Tarski, states that a first-order sentence $ϕ$ is preserved under homomorphisms between structures if, and only if, it is equivalent to an existential positive sentence $ψ$. Given a notion of (syntactic) complexity of sentences, an "equi-resource" homomorphism preservation theorem improves on the classical result by ensuring that $ψ$ can be chosen so that its complexity does not exceed that of $ϕ$. We describe an axiomatic approach to equi-resource homomorphism preservation theorems based on the notion of arboreal category. This framework is then employed to establish novel homomorphism preservation results, and improve on known ones, for various logic fragments, including first-order, guarded and modal logics.
