论文标题
一阶逻辑的有限和前缀类别的扩展保存
Extension Preservation in the Finite and Prefix Classes of First Order Logic
论文作者
论文摘要
众所周知，经典的-tarski保存定理在有限的情况下失败：在一阶逻辑存在的存在片段中，在扩展中封闭的一阶可定义类别的有限结构都无法定义。我们通过为每$ n $，一阶确定的有限结构构建，在扩展程序下构造的有限结构，而$ n $量词的交替是不可定义的。我们构建的类在否定的数据范围内以及及物偏置逻辑的存在片段中可以定义。这是罗森和温斯坦提出的一个否定问题。
It is well known that the classic Łoś-Tarski preservation theorem fails in the finite: there are first-order definable classes of finite structures closed under extensions which are not definable (in the finite) in the existential fragment of first-order logic. We strengthen this by constructing for every $n$, first-order definable classes of finite structures closed under extensions which are not definable with $n$ quantifier alternations. The classes we construct are definable in the extension of Datalog with negation and indeed in the existential fragment of transitive-closure logic. This answers negatively an open question posed by Rosen and Weinstein.
