一句话:刻画 Gaifman 正规形中局部句子的正布尔组合,证明其恰好对应局部初等嵌入下保持的一阶句子。
本文研究一阶逻辑中 Gaifman 正规形的一个片段,即基本局部句子的正布尔组合的表达力。作者证明该片段恰好刻画在局部初等嵌入下保持的一阶句子,从而给出新的一般保持定理,并推广 Łó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 Łó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.