论文标题
一阶逻辑的两变量片段中的订单不变性
Order-Invariance in the Two-Variable Fragment of First-Order Logic
论文作者
论文摘要
我们研究了有序不变的一阶逻辑的两变量片段的表达能力。该逻辑以两种方式脱离了一阶逻辑：首先，公式只能在两个变量上量化。其次，公式可以使用附加的二进制关系，该关系在审查的结构中解释为线性顺序，前提是句子对有限结构的真实价值不取决于在其域上选择哪个线性顺序。我们证明，在有界度的结构类别上，在此逻辑中表达的任何属性均在一阶逻辑中可以定义。然后，当我们将计数量词添加到此逻辑中时，我们表明情况保持不变。
We study the expressive power of the two-variable fragment of order-invariant first-order logic. This logic departs from first-order logic in two ways: first, formulas are only allowed to quantify over two variables. Second, formulas can use an additional binary relation, which is interpreted in the structures under scrutiny as a linear order, provided that the truth value of a sentence over a finite structure never depends on which linear order is chosen on its domain. We prove that on classes of structures of bounded degree, any property expressible in this logic is definable in first-order logic. We then show that the situation remains the same when we add counting quantifiers to this logic.
