论文标题
当区域遇到保存时
When Locality Meets Preservation
论文作者
论文摘要
本文调查了Gaifman正常形式的一阶句子片段的表现力，即基本局部句子的积极布尔组合。我们表明，它们与保留在本地基本嵌入式下的一阶句子完全匹配，从而提供了新的一般保存定理并扩展了Lós-Tarski定理。 这个完整的保存结果在有限的情况下像往常一样失败，我们还表明，自然相关的决策问题是不可决定的。在更受限制的扩展条件下，它仍然产生了有限结构的新行为类别：我们表明，在且仅当它在本地持有时，扩展下的保存才能保持。
This paper investigates the expressiveness of a fragment of first-order sentences in Gaifman normal form, namely the positive Boolean combinations of basic local sentences. We show that they match exactly the first-order sentences preserved under local elementary embeddings, thus providing a new general preservation theorem and extending the Lós-Tarski Theorem. This full preservation result fails as usual in the finite, and we show furthermore that the naturally related decision problems are undecidable. In the more restricted case of preservation under extensions, it nevertheless yields new well-behaved classes of finite structures: we show that preservation under extensions holds if and only if it holds locally.
